OP-01071 Open

Strongly polynomial linear programming

Khachiyan and Karmarkar showed that linear programming is weakly polynomial, that is, solvable in time polynomial in the bit length of the input. Matoušek, Sharir and Welzl gave a randomized algorithm with a subexponential bound. In every fixed dimension the problem can be solved in strongly polynomial time linear in the input size, as Dyer showed in dimensions two and three and Megiddo in all fixed dimensions.

Problem. Is linear programming solvable in strongly polynomial time?

Source: Megiddo (1982, 1983); Problem 8 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary: OC — Optimization and Control
Secondary: MG
Keywords: linear programming, strongly polynomial algorithm, The Open Problems Project

References

@article{megiddo1982,
  author  = {Megiddo, N.},
  title   = {Is binary encoding appropriate for the problem-language relationship?},
  journal = {Theoret. Comput. Sci.},
  volume  = {19},
  year    = {1982},
  pages   = {337--341},
}
@article{megiddo1983,
  author  = {Megiddo, N.},
  title   = {Towards a genuinely polynomial algorithm for linear programming},
  journal = {SIAM J. Comput.},
  volume  = {12},
  year    = {1983},
  pages   = {347--353},
}
@article{khachiyan1980,
  author  = {Khachiyan, L. G.},
  title   = {Polynomial algorithm in linear programming},
  journal = {U.S.S.R. Comput. Math. and Math. Phys.},
  volume  = {20},
  year    = {1980},
  pages   = {53--72},
}
@article{karmarkar1984,
  author  = {Karmarkar, N.},
  title   = {A new polynomial-time algorithm for linear programming},
  journal = {Combinatorica},
  volume  = {4},
  year    = {1984},
  pages   = {373--395},
}
@article{matousek1996,
  author  = {Matou{\v s}ek, J. and Sharir, Micha and Welzl, Emo},
  title   = {A subexponential bound for linear programming},
  journal = {Algorithmica},
  volume  = {16},
  year    = {1996},
  pages   = {498--516},
}
@article{dyer1984,
  author  = {Dyer, M. E.},
  title   = {Linear time algorithms for two- and three-variable linear programs},
  journal = {SIAM J. Comput.},
  volume  = {13},
  year    = {1984},
  pages   = {31--45},
}
@article{megiddo1984,
  author  = {Megiddo, N.},
  title   = {Linear programming in linear time when the dimension is fixed},
  journal = {J. Assoc. Comput. Mach.},
  volume  = {31},
  year    = {1984},
  pages   = {114--127},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01071, "Strongly polynomial linear programming", clopen.solutions.