Linear Programming: Strongly Polynomial?

Is linear programming strongly polynomial?

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

Linear Programming: Strongly Polynomial?

Coming soon

Organizer