Polynomial algorithms for linear programming over the algebraic numbers (Q1343466)

Linear programming (LP) is the problem of maximizing \(cx\) \((c\), a fixed \(n\)-vector), subject to \(Ax \Leftarrow b\) \((A\), a fixed \(m\) by \(n\) matrix and \(b\) a fixed \(m\)-vector). The dimension of a problem instance is the total number of entries in the vectors and matrices that define the instance (above: \(mn + n + m)\). The size of a problem instance is the total number of bits needed to encode these entries in binary notation. An algorithm for LP is said to be polynomial time, if its running time is bounded by a polynomial in the dimension plus the size of the input instance. In 1979, Khachiyan solved a long-standing open problem by presenting a polynomial-time algorithm for rational LPs (i.e., when all entries of the LP instance are rational numbers). Indeed, both Khachiyan's ellipsoid method and Karmarker's interior-point method solve rational LPs in polynomial time (in the above sense). Unfortunately, these results do not extend to LPs with arbitrary real numbers as coefficients. One problem is that there seems to be no useful concept of size for (nonrational) real numbers. In this paper the author derive complexity bounds for LPs with coefficients in the set of algebraic numbers. They utilize results from algebra and number theory to define a useful measure of size for input coefficients. Then they present an algorithm, fashioned after the ellipsoid algorithm of Khachiyan, that runs in polynomial time in the dimension plus the degree of the extension defined by the input coefficients plus the size of the input instance.