Affordable Access

The existence of a strongly polynomial time simplex method

Authors
  • Yan, Zi-zong
  • Li, Xiang-jun
  • Guo, Jinhai
Type
Preprint
Publication Date
Aug 11, 2021
Submission Date
Jun 19, 2020
Source
University of Michigan Library Repository
License
Green
External links

Abstract

It is well known how to clarify whether there is a polynomial time simplex algorithm for linear programming (LP) is the most challenging open problem in optimization and discrete geometry. This paper gives a affirmative answer to this open question by the use of the parametric analysis technique that we recently proposed. We show that there is a simplex algorithm whose number of pivoting steps does not exceed the number of variables of a LP problem.

Report this publication

Statistics

Seen <100 times