next up previous
Next: Problem 9: Edge-Unfolding Convex Up: The Open Problems Project Previous: Problem 7: k-sets


Problem 8: Linear Programming: Strongly Polynomial?

Statement
Is linear programming strongly polynomial?
Origin
Nimrod Megiddo [Meg82][Meg83].
Status/Conjectures
Open.
Partial and Related Results
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].
Appearances
[MO01]
Categories
linear programming
Entry Revision History
J. O'Rourke, 2 Aug 2001, 16 Jul 2007; E. Demaine, 12 Mar 2010.

Bibliography

Dye84
M. E. Dyer.
Linear time algorithms for two- and three-variable linear programs.
SIAM J. Comput., 13:31-45, 1984.

Kar84
N. Karmarkar.
A new polynomial-time algorithm for linear programming.
Combinatorica, 4:373-395, 1984.

Kha80
L. G. Khachiyan.
Polynomial algorithm in linear programming.
U.S.S.R. Comput. Math. and Math. Phys., 20:53-72, 1980.

Meg82
N. Megiddo.
Is binary encoding appropriate for the problem-language relationship?
Theoret. Comput. Sci., 19:337-341, 1982.

Meg84
N. Megiddo.
Linear programming in linear time when the dimension is fixed.
J. Assoc. Comput. Mach., 31:114-127, 1984.

Meg83
N. Megiddo.
Towards a genuinely polynomial algorithm for linear programming.
SIAM J. Comput., 12:347-353, 1983.

MO01
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.

MSW96
J. Matoušek, Micha Sharir, and Emo Welzl.
A subexponential bound for linear programming.
Algorithmica, 16:498-516, 1996.



The Open Problems Project - December 08, 2012