License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.51
URN: urn:nbn:de:0030-drops-63316
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6331/
Go to the corresponding LIPIcs Volume Portal

Hansen, Thomas Dueholm ; Zwick, Uri

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

pdf-format:
LIPIcs-ICALP-2016-51.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{hansen_et_al:LIPIcs:2016:6331,
  author =	{Thomas Dueholm Hansen and Uri Zwick},
  title =	{{Random-Edge Is Slower Than Random-Facet on Abstract Cubes}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6331},
  URN =		{urn:nbn:de:0030-drops-63316},
  doi =		{10.4230/LIPIcs.ICALP.2016.51},
  annote =	{Keywords: Linear programming, the Simplex Algorithm, Pivoting rules, Acyclic Unique Sink Orientations}
}

Keywords: Linear programming, the Simplex Algorithm, Pivoting rules, Acyclic Unique Sink Orientations
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI