Simplex algorithm: Difference between revisions

Revision as of 23:52, 10 November 2020

Revision as of 21:34, 25 November 2020

Line 280:

</ref>

In 20182014, it was proved that a particular variant of the simplex method is [[NP-mighty]], i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution. Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both [[NP-hardness|NP-hard]] problems.<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=The Simplex Algorithm Is NP-Mighty|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> ComputingAt about the outputsame oftime someit otherwas shown that there exists an artificial pivot rulesrule wasfor alreadywhich knowncomputing toits beoutput is [[PSPACE-complete]].<ref>{{Citation | last1 = Adler | first1 = Ilan | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = On Simplex Pivoting Rules and Complexity Theory | journal = International Conference on Integer Programming and Combinatorial Optimization | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref>. In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is [[PSPACE-complete]].<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = The Complexity of the Simplex Method | journal = Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>

Analyzing and quantifying the observation that the simplex algorithm is efficient in practice despite its exponential worst-case complexity has led to the development of other measures of complexity. The simplex algorithm has polynomial-time [[Best, worst and average case|average-case complexity]] under various [[probability distribution]]s, with the precise average-case performance of the simplex algorithm depending on the choice of a probability distribution for the [[random matrix|random matrices]].<ref name="Schrijver" >[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{isbn|0-471-98232-6}} (mathematical)</ref><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|___location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467}}</ref> Another approach to studying "[[porous set|typical phenomena]]" uses [[Baire category theory]] from [[general topology]], and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps.{{Citation needed|date=June 2019}} Another method to analyze the performance of the simplex algorithm studies the behavior of worst-case scenarios under small perturbation – are worst-case scenarios stable under a small change (in the sense of [[structural stability]]), or do they become tractable? This area of research, called [[smoothed analysis]], was introduced specifically to study the simplex method. Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the perturbations.<ref>{{Cite book | last1=Spielman | first1=Daniel | last2=Teng | first2=Shang-Hua | author2-link=Shanghua Teng | title=Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing | publisher=ACM | isbn=978-1-58113-349-3 | doi=10.1145/380752.380813 | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time| pages=296–305 | arxiv=cs/0111050| s2cid=1471 }}</ref>