Dyadic linear programming and extensions
研究如何在线性规划中找到所有分量均为二元有理数的解，给出多项式时间算法，并分析解的支持集大小和分母大小，将算法框架推广到更一般的情形。
Abstract A rational number is dyadic if it has a finite binary representation $$p/2^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:msup> </mml:mrow> </mml:math> , where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are dyadic rationals. We study the problem of finding a dyadic optimal solution to a linear program, if one exists. We show how to solve dyadic linear programs in polynomial time. We give bounds on the size of the support of a solution as well as on the size of the denominators. We identify properties that make the solution of dyadic linear programs possible: closure under addition and negation, and density, and we extend the algorithmic framework beyond the dyadic case.