Next: Problem 9: Edge-Unfolding Convex Polyhedra
Previous: Problem 7: k-sets
Is linear programming strongly polynomial?
Nimrod Megiddo [Meg82][Meg83].
It is known to be weakly polynomial, that is, polynomial in the bit complexity of the input data [Kha80], [Kar84]. Subexponential time is achievable via a randomized algorithm [MSW96]. In any fixed dimension, linear programming can be solved in strongly polynomial linear time (linear in the input size), established in dimensions 2 and 3 in [Dye84] and for all dimensions in [Meg84].
J. O’Rourke, 2 Aug 2001, 16 Jul 2007; E. Demaine, 12 Mar 2010.
M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput., 13:31–45, 1984.
N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373–395, 1984.
L. G. Khachiyan. Polynomial algorithm in linear programming. U.S.S.R. Comput. Math. and Math. Phys., 20:53–72, 1980.
N. Megiddo. Is binary encoding appropriate for the problem-language relationship? Theoret. Comput. Sci., 19:337–341, 1982.
N. Megiddo. Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach., 31:114–127, 1984.
N. Megiddo. Towards a genuinely polynomial algorithm for linear programming. SIAM J. Comput., 12:347–353, 1983.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.
J. Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16:498–516, 1996.