Linear Programming: Strongly Polynomial?

Determine whether linear programming is strongly polynomial. The source contrasts this with weak polynomiality, defined there as running time polynomial in the bit complexity of the input data, but does not specify a more detailed computational model for the open question.

Download

Abstract

The open problem is whether linear programming admits a strongly polynomial algorithm. Linear programming is known to be weakly polynomial, meaning polynomial in the bit complexity of the input, and strongly polynomial linear-time algorithms are known when the dimension is fixed.

Background and progress

The question originated with Megiddo [Megiddo, 1982, Megiddo, 1983]. Polynomial dependence on the bit complexity of the input was established by weakly polynomial algorithms [Khachiyan, 1980, Karmarkar, 1984]. A randomized subexponential-time algorithm is also known [Matou\vsek et al., 1996].

When the dimension is fixed, the picture is stronger. Linear-time strongly polynomial algorithms were established first in dimensions two and three [Dyer, 1984] and then in every fixed dimension [Megiddo, 1984]. The unrestricted strongly polynomial question remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p8.

Reference papers

Linear time algorithms for two- and three-variable linear programsM. E. DyerSIAM J. Comput. · 1984
A new polynomial-time algorithm for linear programmingN. KarmarkarCombinatorica · 1984
Polynomial algorithm in linear programmingL. G. KhachiyanU.S.S.R. Comput. Math. and Math. Phys. · 1980
A subexponential bound for linear programmingJ. Matoušek, Micha Sharir, Emo WelzlAlgorithmica · 1996
Is binary encoding appropriate for the problem-language relationship?N. MegiddoTheoret. Comput. Sci. · 1982
Towards a genuinely polynomial algorithm for linear programmingN. MegiddoSIAM J. Comput. · 1983
Linear programming in linear time when the dimension is fixedN. MegiddoJ. Assoc. Comput. Mach. · 1984