{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:42:14Z","timestamp":1767984134846,"version":"3.49.0"},"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":"https:\/\/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"],"award-info":[{"award-number":["SK 58\/10-2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\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            <jats:italic>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","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Simplex Algorithm Is NP-Mighty"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2085-0454","authenticated-orcid":false,"given":"Yann","family":"Disser","sequence":"first","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"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.","unstructured":"I. Adler , C. H. Papadimitriou , and A. Rubinstein . 2014. On simplex pivoting rules and complexity theory . In Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Springer, 13--24 . I. Adler, C. H. Papadimitriou, and A. Rubinstein. 2014. On simplex pivoting rules and complexity theory. In Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization (IPCO). Springer, 13--24."},{"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.","unstructured":"N. Amenta and G. M. Ziegler . 1996. Deformed products and maximal shadows of polytopes . In 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 . N. Amenta and G. M. Ziegler. 1996. Deformed products and maximal shadows of polytopes. In 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."},{"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.","unstructured":"G. B. Dantzig . 1951. Maximization of a linear function of variables subject to linear inequalities . In Activity Analysis of Production and Allocation -- Proceedings of a Conference, Tj . C. Koopmans (Ed.). Wiley , 339--347. G. B. Dantzig. 1951. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation -- Proceedings of a Conference, Tj. C. Koopmans (Ed.). Wiley, 339--347."},{"key":"e_1_2_1_5_1","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B.","unstructured":"G. B. Dantzig . 1962. Linear Programming and Extensions . Princeton University Press . G. B. Dantzig. 1962. Linear Programming and Extensions. Princeton University Press."},{"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.","unstructured":"Y. Disser and M. Skutella . 2015. The simplex algorithm is NP-mighty . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 858--872 . Y. Disser and M. Skutella. 2015. The simplex algorithm is NP-mighty. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 858--872."},{"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.","unstructured":"J. Fearnley and R. Savani . 2016. The complexity of all-switches strategy improvement . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 130--139 . J. Fearnley and R. Savani. 2016. The complexity of all-switches strategy improvement. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 130--139."},{"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","unstructured":"M. Iri . 1960 . A new method of solving transportation-network problems . Journal of the Operations Research Society of Japan 3 (1960), 27 -- 87 . M. Iri. 1960. A new method of solving transportation-network problems. Journal of the Operations Research Society of Japan 3 (1960), 27--87.","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","unstructured":"L. G. Khachiyan . 1979 . A polynomial algorithm in linear programming . Soviet Mathematics Doklady 20 (1979), 191 -- 194 . L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20 (1979), 191--194.","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.","unstructured":"T. Roughgarden and J. R. Wang . 2016. The complexity of the k-means method . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) . 78(14). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik. T. Roughgarden and J. R. Wang. 2016. The complexity of the k-means method. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). 78(14). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_27_1","volume-title":"Research Trends in Combinatorial Optimization","author":"Skutella M.","unstructured":"M. Skutella . 2009. An introduction to network flows over time . In Research Trends in Combinatorial Optimization , W. Cook, L. Lov\u00e1sz, and J. Vygen (Eds.). Springer , 451--482. M. Skutella. 2009. An introduction to network flows over time. In Research Trends in Combinatorial Optimization, W. Cook, L. Lov\u00e1sz, and J. Vygen (Eds.). Springer, 451--482."},{"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\/10.1145\/3280847","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3280847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:51Z","timestamp":1750208511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3280847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3280847"],"URL":"https:\/\/doi.org\/10.1145\/3280847","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}