Show simple item record

dc.contributor.author
Gärtner, Bernd
dc.contributor.author
Thomas, Antonis
dc.contributor.editor
Jansen, Klaus
dc.contributor.editor
Mathieu, Claire
dc.contributor.editor
Rolim, José D. P.
dc.contributor.editor
Umans, Chris
dc.date.accessioned
2019-11-06T15:34:16Z
dc.date.available
2017-06-12T18:32:45Z
dc.date.available
2019-11-06T15:34:16Z
dc.date.issued
2016
dc.identifier.isbn
978-3-95977-018-7
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.APPROX-RANDOM.2016.30
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/126567
dc.identifier.doi
10.3929/ethz-b-000126567
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Random edge
en_US
dc.subject
Unique sink orientation
en_US
dc.subject
Random walk
en_US
dc.subject
Reachmap
en_US
dc.subject
Niceness
en_US
dc.title
The Niceness of Unique Sink Orientations
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
60
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
30
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016), and the 20th International Workshop on Randomization and Computation (RANDOM 2016)
en_US
ethz.event.location
Paris, France
en_US
ethz.event.date
September 7-9, 2016
en_US
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.date.deposited
2017-06-12T18:32:54Z
ethz.source
ECIT
ethz.identifier.importid
imp593655223d37749849
ethz.ecitpid
pub:189329
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-17T08:39:29Z
ethz.rosetta.lastUpdated
2024-02-02T09:46:28Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=The%20Niceness%20of%20Unique%20Sink%20Orientations&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2016&rft.volume=60&rft.spage=30&rft.issn=1868-8969&rft.au=G%C3%A4rtner,%20Bernd&Thomas,%20Antonis&rft.isbn=978-3-95977-018-7&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.APPROX-RANDOM.2016.30&rft.btitle=Approximation,%20Randomization,%20and%20Combinatorial%20Optimization.%20Algorithms%20and%20Techniques%20(APPROX/RANDOM%202016)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record