Show simple item record

dc.contributor.author
Milatz, Malte
dc.contributor.editor
Speckmann, Bettina
dc.contributor.editor
Toth, Csaba D.
dc.date.accessioned
2018-07-10T12:15:42Z
dc.date.available
2018-07-01T05:44:29Z
dc.date.available
2018-07-10T12:15:42Z
dc.date.issued
2018
dc.identifier.isbn
978-3-95977-066-8
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.SoCG.2018.60
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/273186
dc.identifier.doi
10.3929/ethz-b-000273186
dc.description.abstract
We show that the pivoting process associated with one line and n points in r-dimensional space may need Omega(log^r n) steps in expectation as n -> infty. The only cases for which the bound was known previously were for r <= 3. Our lower bound is also valid for the expected number of pivoting steps in the following applications: (1) The Random-Edge simplex algorithm on linear programs with n constraints in d = n-r variables; and (2) the directed random walk on a grid polytope of corank r with n facets.
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
polytope
en_US
dc.subject
unique sink orientation
en_US
dc.subject
grid
en_US
dc.subject
random walk
en_US
dc.title
Random walks on polytopes of constant corank
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
34th International Symposium on Computational Geometry (SoCG 2018)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
99
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
60
en_US
ethz.size
14 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
34th International Symposium on Computational Geometry (SoCG 2018)
en_US
ethz.event.location
Budapest, Hungary
en_US
ethz.event.date
June 11-14, 2018
en_US
ethz.identifier.scopus
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)
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
2018-07-01T05:44:29Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-07-10T12:15:47Z
ethz.rosetta.lastUpdated
2024-02-02T05:16:18Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Random%20walks%20on%20polytopes%20of%20constant%20corank&amp;rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&amp;rft.date=2018&amp;rft.volume=99&amp;rft.spage=60&amp;rft.issn=1868-8969&amp;rft.au=Milatz,%20Malte&amp;rft.isbn=978-3-95977-066-8&amp;rft.genre=proceeding&amp;rft_id=info:doi/10.4230/LIPIcs.SoCG.2018.60&amp;rft.btitle=34th%20International%20Symposium%20on%20Computational%20Geometry%20(SoCG%202018)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record