Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Simplex Algorithm Is NP-Mighty

The Simplex Algorithm Is NP-Mighty We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm are NP-mighty. That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This result casts a more favorable light on these algorithms’ 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’s 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

The Simplex Algorithm Is NP-Mighty

Download PDF
19 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-simplex-algorithm-is-np-mighty-gG32lW5xHT
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3280847
Publisher site
See Article on Publisher Site

Abstract

We show that the Simplex Method, the Network Simplex Method—both with Dantzig’s original pivot rule—and the Successive Shortest Path Algorithm are NP-mighty. That is, each of these algorithms can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm’s execution. This result casts a more favorable light on these algorithms’ 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’s 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.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 16, 2018

Keywords: NP-mightiness

References

  • On simplex pivoting rules and complexity theory
    Adler, I.; Papadimitriou, C. H.; Rubinstein, A.
  • Deformed products and maximal shadows of polytopes
    Amenta, N.; Ziegler, G. M.
  • A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns
    Busacker, R. G.; Gowen, P. J.
  • Maximization of a linear function of variables subject to linear inequalities
    Dantzig, G. B.
  • Linear Programming and Extensions
    Dantzig, G. B.
  • The simplex algorithm is NP-mighty
    Disser, Y.; Skutella, M.
  • The simplex algorithm is NP-mighty
    Disser, Y.; Skutella, M.
  • The complexity of the simplex method
    Fearnley, J.; Savani, R.
  • The complexity of all-switches strategy improvement
    Fearnley, J.; Savani, R.
  • Flows in Networks
    Ford, L. R.; Fulkerson, D. R.
  • Transient flows in networks
    Gale, D.
  • Computers and Intractability, A Guide to the Theory of NP-Completeness
    Garey, M. R.; Johnson, D. S.
  • The complexity of the homotopy method, equilibrium selection, and lemke-howson solutions
    Goldberg, P. W.; Papdimitriou, C. H.; Savani, R.
  • A new method of solving transportation-network problems
    Iri, M.
  • Some equivalent objectives for dynamic network flow problems
    Jarvis, J. J.; Ratliff, H. D.
  • How easy is local search? Journal of Computer and System Science 37 (1988), 79--100
    Johnson, D. S.; Papadimitriou, C. H.; Yannakakis, M.
  • A new polynomial-time algorithm for linear programming
    Karmarkar, N.
  • A polynomial algorithm in linear programming
    Khachiyan, L. G.
  • Polynomial algorithms in linear programming
    Khachiyan, L. G.
  • How good is the simplex algorithm? In Inequalities III, O
    Klee, V.; Minty, G. J.
  • Equilibrium points of bimatrix games
    Lemke, C. E.; Howson, J. T.
  • Maximal, lexicographic, and dynamic network flows
    Minieka, E.
  • A polynomial time primal network simplex algorithm for minimum cost flows
    Orlin, J. B.
  • On the complexity of the parity argument and other inefficient proofs of existence
    Papadimitriou, C. H.
  • On the complexity of local search
    Papadimitriou, C. H.; Schäffer, A. A.; Yannakakis, M.
  • The complexity of the k-means method
    Roughgarden, T.; Wang, J. R.
  • An introduction to network flows over time
    Skutella, M.
  • Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
    Spielman, D. A.; Teng, S.-H.
  • Tardos
    É,
  • An algorithm for universal maximal dynamic flows in a network
    Wilkinson, W. L.
  • A bad network problem for the simplex method and other minimum cost flow algorithms
    Zadeh, N.