Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
From Bernhard Korte, Jens Vygen, Combinatorial Optimization,
Instances of LINEAR PROGRAMMING are vectors and matrices. Since no strongly polynomial-time algorithm for LINEAR PROGRAMMING is known we have to restrict attention to rational instances when analyzing the running time of algorithms.
I was wondering why does the absence of strongly polynomial time algorithms for linear programming imply restriction to rational instances?
A strongly polynomial algorithm in the context of linear programming probably means an algorithm in the arithmetic model (where numbers can be added, multiplied, compared and so on), whose running time does not depend on the magnitudes of the numbers involved. Such an algorithm could be applied directly for real numbers. Examples of algorithms of this type are the simplex algorithm and the criss-cross algorithm, both really a collection of related algorithms. However, variants of these algorithm are either known not to be polynomial-time, or (in some cases) not known and not expected to be polynomial-time.
Other algorithms for linear programming exist: the ellipsoid algorithm and the interior-point algorithm (again, there are really many variants of these algorithms). The number of iterations in each case depends on the precision needed to guarantee reaching an optimal solution, and that's why they are not strongly polynomial. While these algorithms can also be implemented in the arithmetic model, convergence is no longer guaranteed to take polynomial time.
When the inputs are rational numbers, then the number of iterations needed to converge is polynomial in the length of the input, and therefore these algorithms become polynomial-time.
