**Next:** Problem 9: Edge-Unfolding Convex Polyhedra

**Previous:** Problem 7: k-sets

- Statement
Is linear programming strongly polynomial?

- Origin
- 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
- Categories
linear programming

- Entry Revision History
J. O’Rourke, 2 Aug 2001, 16 Jul 2007; E. Demaine, 12 Mar 2010.

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