Document Open Access Logo

Random-Edge Is Slower Than Random-Facet on Abstract Cubes

Authors Thomas Dueholm Hansen, Uri Zwick

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.51.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Dueholm Hansen
Uri Zwick

Cite As Get BibTex

Thomas Dueholm Hansen and Uri Zwick. Random-Edge Is Slower Than Random-Facet on Abstract Cubes. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.51

Abstract

Random-Edge and Random-Facet are two very natural randomized pivoting rules for the simplex algorithm. The behavior of Random-Facet is fairly well understood. It performs an expected sub-exponential number of pivoting steps on any linear program, or more generally, on any Acyclic Unique Sink Orientation (AUSO) of an arbitrary polytope, making it the fastest known pivoting rule for the simplex algorithm. The behavior of Random-Edge is much less understood. We show that in the AUSO setting, Random-Edge is slower than Random-Facet. To do that, we construct AUSOs of the n-dimensional hypercube on which Random-Edge performs an expected number of 2^{Omega(sqrt(n*log(n)))} steps. This improves on a 2^{Omega(sqrt^3(n))} lower bound of Matoušek and Szabó. As Random-Facet performs an expected number of 2^{O(sqrt(n)} steps on any n-dimensional AUSO, this established our result. Improving our 2^{Omega(sqrt(n*log(n)))} lower bound seems to require radically new techniques.

Subject Classification

Keywords
  • Linear programming
  • the Simplex Algorithm
  • Pivoting rules
  • Acyclic Unique Sink Orientations

Metrics

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

References

  1. N. Amenta and G.M. Ziegler. Deformed products and maximal shadows of polytopes. In Advances in Discrete and Computational Geometry, pages 57-90, Providence, 1996. Amer. Math. Soc. Contemporary Mathematics 223. Google Scholar
  2. D. Avis and V. Chvátal. Notes on Bland’s pivoting rule. In Polyhedral Combinatorics, volume 8 of Mathematical Programming Studies, pages 24-34. Springer, 1978. Google Scholar
  3. V. Chvátal. Linear programming. W. H. Freeman and Company, 1983. Google Scholar
  4. G.B. Dantzig. Linear programming and extensions. Princeton University Press, 1963. Google Scholar
  5. J. Fearnley. Exponential lower bounds for policy iteration. In Proc. of 37th ICALP, pages 551-562, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14162-1_46.
  6. O. Friedmann. An exponential lower bound for the latest deterministic strategy iteration algorithms. Logical Methods in Computer Science, 7(3), 2011. URL: http://dx.doi.org/10.2168/LMCS-7(3:23)2011.
  7. O. Friedmann. A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In Proc. of 15th IPCO, pages 192-206, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20807-2_16.
  8. O. Friedmann, T.D. Hansen, and U. Zwick. A subexponential lower bound for the Random Facet algorithm for parity games. In Proc. of 22nd SODA, pages 202-216, 2011. Google Scholar
  9. O. Friedmann, T.D. Hansen, and U. Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In Proc. of 43th STOC, pages 283-292, 2011. URL: http://dx.doi.org/10.1145/1993636.1993675.
  10. O. Friedmann, T.D. Hansen, and U. Zwick. Errata for: A subexponential lower bound for the random facet algorithm for parity games. CoRR, abs/1410.7871, 2014. URL: http://arxiv.org/abs/1410.7871.
  11. O. Friedmann, T.D. Hansen, and U. Zwick. Random-facet and random-bland require subexponential time even for shortest paths. CoRR, abs/1410.7530, 2014. URL: http://arxiv.org/abs/1410.7530.
  12. B. Gärtner. The Random-Facet simplex algorithm on combinatorial cubes. Random Structures and Algorithms, 20(3):353-381, 2002. URL: http://dx.doi.org/10.1002/rsa.10034.
  13. B. Gärtner and V. Kaibel. Two new bounds for the Random-Edge simplex-algorithm. SIAM J. Discrete Math., 21(1):178-190, 2007. URL: http://dx.doi.org/10.1137/05062370X.
  14. B. Gärtner and A. Thomas. The niceness of unique sink orientations. Unpublished manuscript, 2016. URL: https://sites.google.com/site/antonisthomas/research/niceness.pdf.
  15. D. Goldfarb and W.Y. Sit. Worst case behavior of the steepest edge simplex method. Discrete Applied Mathematics, 1(4):277-285, 1979. Google Scholar
  16. T.D. Hansen, M. Paterson, and U. Zwick. Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. In Proc. of 25th SODA, pages 874-881, 2014. Google Scholar
  17. T.D. Hansen and U. Zwick. An improved version of the Random-Facet pivoting rule for the simplex algorithm. In Proc. of 47th STOC, pages 209-218, 2015. Google Scholar
  18. R. G. Jeroslow. The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Mathematics, 4(4):367-377, 1973. Google Scholar
  19. G. Kalai. A simple way to tell a simple polytope from its graph. Journal of combinatorial theory, Series A, 49(2):381-383, 1988. Google Scholar
  20. G. Kalai. A subexponential randomized simplex algorithm (extended abstract). In Proc. of 24th STOC, pages 475-482, 1992. Google Scholar
  21. G. Kalai. Linear programming, the simplex algorithm and simple polytopes. Mathematical Programming, 79:217-233, 1997. Google Scholar
  22. N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-395, 1984. Google Scholar
  23. L.G. Khachiyan. A polynomial time algorithm in linear programming. Soviet Math. Dokl., 20:191-194, 1979. Google Scholar
  24. V. Klee and G. J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalities III, pages 159-175. Academic Press, New York, 1972. Google Scholar
  25. D.A. Levin, Y. Peres, and E.L. Wilmer. Markov chains and mixing times. American Mathematical Soc., 2009. Google Scholar
  26. Y. Mansour and S.P. Singh. On the complexity of policy iteration. In Proc. of the 15th UAI, pages 401-408, 1999. Google Scholar
  27. J. Matoušek. Lower bounds for a subexponential optimization algorithm. Random Structures and Algorithms, 5(4):591-608, 1994. Google Scholar
  28. J. Matoušek and B. Gärtner. Understanding and using linear programming. Springer, 2007. Google Scholar
  29. J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16(4-5):498-516, 1996. Google Scholar
  30. J. Matoušek and T. Szabó. Random Edge can be exponential on abstract cubes. In Proc. of 45th FOCS, pages 92-100, 2004. Google Scholar
  31. J. Matoušek and T. Szabó. RANDOM EDGE can be exponential on abstract cubes. Advances in Mathematics, 1(204):262-277, 2006. Google Scholar
  32. A. Schrijver. Theory of Linear and Integer Programming. John Wiley &Sons, 1986. Google Scholar
  33. I. Schurr and T. 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.
  34. T. Szabó and E. Welzl. Unique sink orientations of cubes. In Proc. of 42th FOCS, pages 547-555, 2001. Google Scholar
  35. E. Welzl. Towards the peak - problem section. Unpublished manuscript, 2001. URL: http://www.ti.inf.ethz.ch/ew/workshops/01-lc/problems/node7.html.
  36. K. Williamson Hoke. Completely unimodal numberings of a simple polytope. Discrete Applied Mathematics, 20(1):69-81, 1988. URL: http://dx.doi.org/10.1016/0166-218X(88)90042-X.
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