{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T14:59:03Z","timestamp":1641394743074},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alexander von Humboldt-Foundation"},{"name":"DFG Priority Programme 1736 \u201cAlgorithms for Big Data\u201d","award":["SK 58\/10-2"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"\n We show that the Simplex Method, the Network Simplex Method\u2014both with Dantzig\u2019s original pivot rule\u2014and the Successive Shortest Path Algorithm are\n NP-mighty<\/jats:italic>\n . That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in\u00a0NP implicitly during the algorithm\u2019s execution. This result casts a more favorable light on these algorithms\u2019 exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm\u2019s execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.\n <\/jats:p>","DOI":"10.1145\/3280847","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-19","source":"Crossref","is-referenced-by-count":1,"title":["The Simplex Algorithm Is NP-Mighty"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-2085-0454","authenticated-orcid":false,"given":"Yann","family":"Disser","sequence":"first","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Springer, 13--24","author":"Adler I."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference in the Mathematical Sciences, Bernard Chazelle, Jacob E. Goodman and Richard Pollack (Eds.). American Mathematical Society, 57--90","author":"Amenta N."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"R. G. Busacker and P. J. Gowen. 1960. A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns. Technical Paper ORO-TP-15. Operations Research Office The Johns Hopkins University Bethesda Maryland. R. G. Busacker and P. J. Gowen. 1960. A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns. Technical Paper ORO-TP-15. Operations Research Office The Johns Hopkins University Bethesda Maryland.","DOI":"10.21236\/AD0249662"},{"key":"e_1_2_1_4_1","volume-title":"Activity Analysis of Production and Allocation -- Proceedings of a Conference, Tj","author":"Dantzig G. B."},{"key":"e_1_2_1_5_1","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B."},{"key":"e_1_2_1_6_1","unstructured":"Y. Disser and M. Skutella. 2013. The simplex algorithm is NP-mighty. CoRR abs\/1311.5935 (2013). Y. Disser and M. Skutella. 2013. The simplex algorithm is NP-mighty. CoRR abs\/1311.5935 (2013)."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 858--872","author":"Disser Y."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746558"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 130--139","author":"Fearnley J."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"L. R. Ford and D. R. Fulkerson. 1962. Flows in Networks. Princeton University Press. L. R. Ford and D. R. Fulkerson. 1962. Flows in Networks. Princeton University Press.","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998140"},{"key":"e_1_2_1_12_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465769.2465774"},{"key":"e_1_2_1_14_1","first-page":"27","article-title":"A new method of solving transportation-network problems","volume":"3","author":"Iri M.","year":"1960","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.28.1.106"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_18_1","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_2_1_20_1","unstructured":"V. Klee and G. J. Minty. 1972. How good is the simplex algorithm? In Inequalities III O. Shisha (Ed.). Academic Press 159--175. V. Klee and G. J. Minty. 1972. How good is the simplex algorithm? In Inequalities III O. Shisha (Ed.). Academic Press 159--175."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.517"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100274"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","author":"Roughgarden T."},{"key":"e_1_2_1_27_1","volume-title":"Research Trends in Combinatorial Optimization","author":"Skutella M."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579369"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.7.1602"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580132"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3280847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,5]],"date-time":"2022-01-05T02:36:37Z","timestamp":1641350197000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,31]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3280847"],"URL":"http:\/\/dx.doi.org\/10.1145\/3280847","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2019,1,31]]}}}