ZIB

Treffer pro Seite

Treffer 11 - 11 | 11 Treffer

Sortierung

Unbekannt

Two New Bounds for the Random-Edge Simplex Algorithm (2005)

Gärtner, Bernd ; Kaibel, Volker

zur Merkliste hinzufügen auf der Merkliste

Details

Publikationsdatum: 2014-11-21

Beschreibung: We prove that the Random-Edge simplex algorithm requires an expected number of at most $13n/sqrt(d)$ pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of $2^d$ on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d.

Schlagwort(e): ddc:000

Sprache: Englisch

Materialart: reportzib , doc-type:preprint

Format: application/pdf

Format: application/postscript

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

OPUS

PDF

Überblick

Treffer 11 - 11 | 11 Treffer