Document Open Access Logo

The Niceness of Unique Sink Orientations

Authors Bernd Gärtner, Antonis Thomas

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.30.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Bernd Gärtner
Antonis Thomas

Cite As Get BibTex

Bernd Gärtner and Antonis Thomas. The Niceness of Unique Sink Orientations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.30

Abstract

Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001, Welzl introduced the concepts of reachmaps and niceness of Unique Sink Orientations (USO), in an effort to better understand the behavior of Random Edge. In this paper, we initiate the systematic study of these concepts. We settle the questions that were asked by Welzl about the niceness of (acyclic) USO. Niceness implies natural upper bounds for Random Edge and we provide evidence that these are tight or almost tight in many interesting cases. Moreover, we show that Random Edge is polynomial on at least n^{Omega(2^n)} many (possibly cyclic) USO. As a bonus, we describe a derandomization of Random Edge which achieves the same asymptotic upper bounds with respect to niceness.

Subject Classification

Keywords
  • random edge
  • unique sink orientation
  • random walk
  • reachmap
  • niceness

Metrics

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

References

  1. Ilan Adler, Christos H. Papadimitriou, and Aviad Rubinstein. On simplex pivoting rules and complexity theory. In Jon Lee and Jens Vygen, editors, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, volume 8494 of Lecture Notes in Computer Science, pages 13-24. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07557-0_2.
  2. 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.
  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. Yann Disser and Martin Skutella. The simplex algorithm is NP-mighty. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 858-872. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.59.
  5. John Fearnley and Rahul Savani. The complexity of the simplex method. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 201-208. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746558.
  6. John Fearnley and Rahul Savani. The complexity of all-switches strategy improvement. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 130-139. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch10.
  7. 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.
  8. Oliver Friedmann. A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In Oktay Günlük and Gerhard J. Woeginger, editors, Integer Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings, volume 6655 of Lecture Notes in Computer Science, pages 192-206. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20807-2_16.
  9. Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 283-292. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993675.
  10. Bernd Gärtner. The Random-Facet simplex algorithm on combinatorial cubes. Random Structures &Algorithms, 20(3), 2002. URL: http://dx.doi.org/10.1002/rsa.10034.
  11. Bernd Gärtner, Walter D. Morris Jr., and Leo Rüst. Unique sink orientations of grids. Algorithmica, 51(2):200-235, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9090-x.
  12. Bernd Gärtner and Ingo Schurr. Linear programming and unique sink orientations. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 749-757. ACM Press, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109639.
  13. Bernd Gärtner and Antonis Thomas. The complexity of recognizing unique sink orientations. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 341-353. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.341.
  14. Bernd Gärtner and Antonis Thomas. The Niceness of Unique Sink Orientations. CoRR, June 2016. URL: http://arxiv.org/abs/1606.07709.
  15. Peter L. Hammer, Bruno Simeone, Thomas M. Liebling, and Dominique de Werra. From linear separability to unimodality: A hierarchy of pseudo-boolean functions. SIAM J. Discrete Math., 1(2):174-184, 1988. URL: http://dx.doi.org/10.1137/0401019.
  16. Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick. Improved upper bounds for random-edge and random-jump on abstract cubes. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 874-881. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.65.
  17. Thomas Dueholm Hansen and Uri Zwick. Random-edge is slower than random-facet on abstract cubes. To appear in ICALP 2016., 2016. URL: http://cs.au.dk/~tdh/papers/Random-Edge-AUSO.pdf.
  18. Gil Kalai. A subexponential randomized simplex algorithm (extended abstract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 475-482. ACM, 1992. URL: http://dx.doi.org/10.1145/129712.129759.
  19. Lorenz Klaus and Hiroyuki Miyata. Enumeration of PLCP-orientations of the 4-cube. European Journal of Combinatorics, 50:138-151, 2015. Combinatorial Geometries: Matroids, Oriented Matroids and Applications. Special Issue in Memory of Michel Las Vergnas. URL: http://dx.doi.org/10.1016/j.ejc.2015.03.010.
  20. Victor Klee and George J. Minty. How good is the simplex algorithm? Inequalities III, pages 159-175, 1972. Google Scholar
  21. 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.
  22. 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.
  23. 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.
  24. 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.1109/FOCS.2004.56.
  25. Walter D. Morris Jr. Randomized pivot algorithms for P-matrix linear complementarity problems. Mathematical Programming, 92(2):285-296, 2002. URL: http://dx.doi.org/10.1007/s101070100268.
  26. 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.
  27. Ingo Schurr and Tibor Szabó. Jumping doesn't help in abstract cubes. In Michael Jünger and Volker Kaibel, editors, Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, 2005, volume 3509 of LNCS, pages 225-235. Springer, 2005. URL: http://dx.doi.org/10.1007/11496915_17.
  28. 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.
  29. Tibor Szabó and Emo Welzl. Unique sink orientations of cubes. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 547-555. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959931.
  30. Emo Welzl. i-Niceness. http://www.ti.inf.ethz.ch/ew/workshops/01-lc/problems/node7.html, 2001.
  31. Kathy 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