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, exponential 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.

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.