iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-319-07557-0_2
On Simplex Pivoting Rules and Complexity Theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Simplex Pivoting Rules and Complexity Theory

  • Conference paper
Integer Programming and Combinatorial Optimization (IPCO 2014)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8494))

Abstract

We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm’s path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig’s shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adler, I., Karp, R.M., Shamir, R.: A Family of Simplex Variants Solving an m x d Linear Program in Expected Number of Pivot Steps Depending on d Only. Mathematics of Operations Research 11(4), 570–590 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  2. Adler, I., Megiddo, N.: A Simplex Algorithm whose Average Number of Steps is Bounded between Two Quadratic Functions of the Smaller Dimension. Journal of the ACM 32(4), 471–495 (1985)

    Article  MathSciNet  Google Scholar 

  3. Amenta, N., Ziegler, G.: Deformed products and maximal shadows of polytopes. In: Advances in Discrete and Computational Geometry, pp. 57–90 (1996)

    Google Scholar 

  4. Avis, D., Chvatal, C.: Notes on Bland’s Pivoting Rule. Math. Programming Study 8, 24–34 (1978)

    Article  Google Scholar 

  5. Borgwardt, K.H.: The Average Number of Steps Required by the Simplex Method is Polynomial. Zeitschrift fur Operations Research 26(1), 157–177 (1982)

    MATH  MathSciNet  Google Scholar 

  6. Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(2), 533–570 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  7. Cottle, R., Pang, J.-S., Stone, R.E.: The linear complementarity problem. Academic Press (1992)

    Google Scholar 

  8. Dantzig, G.B.: Maximization of a Linear Function of Variables subject to Linear Inequalities (1947); Published in Koopmans, T.C. (ed.): Activity Analysis of Production and Allocation, pp. 339–347. Wiley & Chapman-Hall (1951)

    Google Scholar 

  9. Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press and the RAND Corporation (1963)

    Google Scholar 

  10. Danzig, G.B., Ford, L.R., Fulkerson, D.R.: A Primal-Dual Algorithm for Linear Programming. In: Kuhn, H.W., Tucker, A.W. (eds.) Linear Inequalities and Related Systems, pp. 171–181. Princeton University Press (1954)

    Google Scholar 

  11. Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2), 248–264 (1972)

    Article  MATH  Google Scholar 

  12. Fukuda, K., Matsui, T.: On the Finiteness of the Criss-cross Method. European Journal of Operations Research 52, 119–124 (1991)

    Article  MATH  Google Scholar 

  13. Goldberg, P.W., Papadimitriou, C.H., Savani, R.: The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation 1(2), Article 9 (2013)

    Google Scholar 

  14. Goldfarb, D., Reid, J.K.: A Practical Steepest-Edge Simplex Algorithm. Mathematical Programming 12, 361–371 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  15. Jeroslow, R.G.: The Simplex Algorithm with the Pivot Rule of Maximizing Criterion Improvement. Discrete Mathematics 4, 367–377 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kalai, G.: A Subexponential Randomized Simplex Algorithm. In: ACM 24th Symposium on Theory of Computing, pp. 475–482 (1992)

    Google Scholar 

  17. Kalai, G., Kleitman, D.: Quasi-polynomial Bounds for the Diameter of Graphs and Polyhedra. Bull. Amer. Math. Soc. 26, 315–316 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  18. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  19. Karmarkar, N.K.: A New Polynomial-time Algorithm for Linear Programming. Combinatorica 4, 373–395 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  20. Khachian, R.M.: A Polynomial Algorithm in Linear Programming. Doklady Akad. Nauk SSSR 244(5), 1093–1096; Translated in Soviet Math. Doklady, 20, 191–194 (1979)

    Google Scholar 

  21. Klee, V., Minty, G.J.: How Good is the Simplex Algorithm? In: Shisha, O. (ed.) Inequalities III, pp. 159–175. Academic Press, New York (1972)

    Google Scholar 

  22. Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics 12(2), 413–423 (1996)

    Article  MathSciNet  Google Scholar 

  23. Matousek, J., Sharir, M., Welzl, E.: A Subexponential Bound for Linear programming. Algorithmica 16(4-5), 498–516 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  24. Murty, K.G.: Computational Complexity of Parametric Linear Programming. Mathematical Programming 19, 213–219 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  25. Papadimitriou, C.: Computational Complexity. Addison Wesley (1994)

    Google Scholar 

  26. Ross, C.: An Exponential Example for Terlaky’s Pivoting Rule for the Criss-cross Simplex Method. Mathematical Programming 46, 78–94 (1990)

    Google Scholar 

  27. Santos, F.: A Counterexample to the Hirsch Conjecture. Annals of Mathematics 176(1), 383–412 (2013)

    Article  Google Scholar 

  28. Smale, S.: On the Average Number of Steps of the Simplex Method of Linear Programming. Mathematical Programming 27, 241–267 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  29. Spielman, D.A., Teng, S.-H.: Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM 51(3), 385–463 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  30. Tardos, E.: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs. Operations Research 34, 250–256 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  31. Savani, R., von Stengel, B.: Hard to Solve Bimatrix Games. Econometrica 74(2), 397–429 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  32. Terlaky, T.: A Convergent Criss-cross Method. Optimization 16, 683–690 (1990)

    Article  MathSciNet  Google Scholar 

  33. Todd, M.J.: Polynomial Expected Behvior of Pivoting Algorithm for Linear Complementarity and Linear Programming Problems. Mathematical Programming 35, 173–192 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  34. Ye, Y.: The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate. Mathematics of Operations Research 36(4), 593–603 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  35. Zionts, S.: The Criss-cross Method for Solving Linear Programming Problems. Management Science 15, 426–445 (1979)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Berkeley, CA, 94720, USA

    Ilan Adler, Christos Papadimitriou & Aviad Rubinstein

Authors
  1. Ilan Adler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christos Papadimitriou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aviad Rubinstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Industrial and Operations Engineering, University of Michigan, Beal Avenue, 1205, Ann Arbor, MI, USA

    Jon Lee

  2. Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, P.O. Box, 53113, Bonn, Germany

    Jens Vygen

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer International Publishing Switzerland

About this paper

Cite this paper

Adler, I., Papadimitriou, C., Rubinstein, A. (2014). On Simplex Pivoting Rules and Complexity Theory. In: Lee, J., Vygen, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2014. Lecture Notes in Computer Science, vol 8494. Springer, Cham. https://doi.org/10.1007/978-3-319-07557-0_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-07557-0_2

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-07556-3

  • Online ISBN: 978-3-319-07557-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation