Document Open Access Logo

Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes

Author Antonis Thomas

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.69.pdf
  • Filesize: 0.65 MB
  • 14 pages

Document Identifiers

Author Details

Antonis Thomas

Cite As Get BibTex

Antonis Thomas. Exponential Lower Bounds for History-Based Simplex Pivot Rules on Abstract Cubes. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.69

Abstract

The behavior of the simplex algorithm is a widely studied subject. Specifically, the question of the existence of a polynomial pivot rule for the simplex algorithm is of major importance. Here, we give exponential lower bounds for three history-based pivot rules. Those rules decide their next step based on memory of the past steps. In particular, we study Zadeh's least entered rule, Johnson's least-recently basic rule and Cunningham's least-recently considered (or round-robin) rule. We give exponential lower bounds on Acyclic Unique Sink Orientations of the abstract cube, for all of these pivot rules. For Johnson's rule our bound is the first superpolynomial one in any context; for Zadeh's it is the first one for AUSO. Those two are our main results.

Subject Classification

Keywords
  • pivot rule
  • lower bound
  • exponential
  • unique sink orientation
  • zadeh

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yoshikazu Aoshima, David Avis, Theresa Deering, Yoshitake Matsumoto, and Sonoko Moriyama. On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes. Discrete Applied Mathematics, 160(15):2104-2115, 2012. URL: http://dx.doi.org/10.1016/j.dam.2012.05.023.
  2. David Avis and Oliver Friedmann. An exponential lower bound for cunningham’s rule. Mathematical Programming, pages 1-35, 2016. URL: http://dx.doi.org/10.1007/s10107-016-1008-4.
  3. József Balogh and Robin Pemantle. The Klee-Minty random edge chain moves with linear speed. Random Structures &Algorithms, 30(4):464-483, 2007. URL: http://dx.doi.org/10.1002/rsa.20127.
  4. William H Cunningham. Theoretical properties of the network simplex method. Mathematics of Operations Research, 4(2):196-208, 1979. URL: http://dx.doi.org/10.1287/moor.4.2.196.
  5. Jan Foniok, Bernd Gärtner, Lorenz Klaus, and Markus Sprecher. Counting unique-sink orientations. Discrete Applied Mathematics, 163, Part 2:155-164, 2014. URL: http://dx.doi.org/10.1016/j.dam.2013.07.017.
  6. Oliver Friedmann. A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In IPCO 2011, pages 192-206, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20807-2_16.
  7. Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In STOC 2011, pages 283-292, 2011. URL: http://dx.doi.org/10.1145/1993636.1993675.
  8. Bernd Gärtner. A subexponential algorithm for abstract optimization problems. SIAM J. Comput., 24(5):1018-1035, 1995. URL: http://dx.doi.org/10.1137/S0097539793250287.
  9. Bernd Gärtner. The random-facet simplex algorithm on combinatorial cubes. Random Structures &Algorithms, 20(3):353-381, 2002. URL: http://dx.doi.org/10.1002/rsa.10034.
  10. Bernd Gärtner, Martin Henk, and Günter M. Ziegler. Randomized simplex algorithms on Klee-Minty cubes. Combinatorica, 18(3):349-372, 1998. URL: http://dx.doi.org/10.1007/PL00009827.
  11. Bernd Gärtner and Antonis Thomas. The complexity of recognizing unique sink orientations. In STACS 2015, pages 341-353, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.341.
  12. Bernd Gärtner and Antonis Thomas. The niceness of unique sink orientations. In APPROX/RANDOM 2016, pages 30:1-30:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.30.
  13. Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick. Improved upper bounds for random-edge and random-jump on abstract cubes. In SODA 2014, pages 874-881, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.65.
  14. Thomas Dueholm Hansen and Uri Zwick. Random-edge is slower than random-facet on abstract cubes. In ICALP 2016, pages 51:1-51:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.51.
  15. Gil Kalai. A subexponential randomized simplex algorithm (extended abstract). In STOC 1992, pages 475-482, 1992. URL: http://dx.doi.org/10.1145/129712.129759.
  16. Victor Klee and George J. Minty. How good is the simplex algorithm? Inequalities III, pages 159-175, 1972. Google Scholar
  17. Jiří Matoušek. Lower bounds for a subexponential optimization algorithm. Random Structures &Algorithms, 5(4):591-607, 1994. URL: http://dx.doi.org/10.1002/rsa.3240050408.
  18. Jiří Matoušek. The number of unique-sink orientations of the hypercube*. Combinatorica, 26(1):91-99, 2006. URL: http://dx.doi.org/10.1007/s00493-006-0007-0.
  19. Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4/5):498-516, 1996. URL: http://dx.doi.org/10.1007/BF01940877.
  20. Jiří Matoušek and Tibor Szabó. RANDOM EDGE can be exponential on abstract cubes. Advances in Mathematics, 204(1):262-277, 2006. URL: http://dx.doi.org/10.1016/j.aim.2005.05.021.
  21. Ingo Schurr and Tibor Szabó. Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes. Discrete & Computational Geometry, 31(4):627-642, 2004. URL: http://dx.doi.org/10.1007/s00454-003-0813-8.
  22. Ingo Schurr and Tibor Szabó. Jumping doesn't help in abstract cubes. In IPCO 2005, pages 225-235, 2005. URL: http://dx.doi.org/10.1007/11496915_17.
  23. Alan Stickney and Layne Watson. Digraph models of Bard-type algorithms for the linear complementarity problem. Math. Oper. Res., 3(4):322-333, 1978. URL: http://dx.doi.org/10.1287/moor.3.4.322.
  24. Tibor Szabó and Emo Welzl. Unique sink orientations of cubes. In FOCS 2001, pages 547-555, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959931.
  25. Antonis Thomas. Exponential lower bounds for history-based simplex pivot rules on abstract cubes. CoRR, abs/1706.09380, 2017. URL: https://arxiv.org/abs/1706.09380.
  26. Norman Zadeh. What is the worst case behavior of the simplex algorithm. Polyhedral computation, 48:131-143, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact