The Open Problems Project

Next: Problem 9: Edge-Unfolding Convex Polyhedra

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.