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.APPROX-RANDOM.2016.30
URN: urn:nbn:de:0030-drops-66538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6653/
Go to the corresponding LIPIcs Volume Portal

Gärtner, Bernd ; Thomas, Antonis

The Niceness of Unique Sink Orientations

pdf-format:
LIPIcs-APPROX-RANDOM-2016-30.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{grtner_et_al:LIPIcs:2016:6653,
  author =	{Bernd G{\"a}rtner and Antonis Thomas},
  title =	{{The Niceness of Unique Sink Orientations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6653},
  URN =		{urn:nbn:de:0030-drops-66538},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.30},
  annote =	{Keywords: random edge, unique sink orientation, random walk, reachmap, niceness}
}

Keywords: random edge, unique sink orientation, random walk, reachmap, niceness
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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