Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
It may be because time complexity analysis on real numbers is a lot harder to define? Restricting to finite-size objects like rational is one way to talk about complexity. –  jmad Dec 17 '12 at 19:34
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.