article

Two New Bounds for the Random-Edge Simplex-Algorithm

Authors:

Bernd Ga¨rtner,

Volker KaibelAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 21, Issue 1

Pages 178 - 190

https://doi.org/10.1137/05062370X

Published: 01 February 2007 Publication History

Abstract

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 the factor $1/d^{(1-\varepsilon)\log d}$ for every $\varepsilon>0$.

Cited By

View all

Nannicini G(2024)Fast Quantum Subroutines for the Simplex MethodOperations Research10.1287/opre.2022.234172:2(763-780)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2341
Dumitrescu AMandal RTóth C(2018)Monotone Paths in Geometric TriangulationsTheory of Computing Systems10.5555/3231788.323179862:6(1490-1524)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.5555/3231788.3231798
Eisenbrand FVempala S(2017)Geometric random edgeMathematical Programming: Series A and B10.1007/s10107-016-1089-0164:1-2(325-339)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10107-016-1089-0
Show More Cited By

Index Terms

Two New Bounds for the Random-Edge Simplex-Algorithm
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Improved upper bounds for random-edge and random-jump on abstract cubes
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

Upper bounds are given for the complexity of two very natural randomized algorithms for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of the n-cube. For Random-Edge, we obtain an upper bound of about 1.80ⁿ, improving upon the the ...
Lollipop and cubic weight functions for graph pebbling
Abstract
Given a configuration of pebbles on the vertices of a graph G, a pebbling move removes two pebbles from a vertex and puts one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest number of pebbles required such that, ... $_{}$
New Bounds and Constructions for Granular Media Coding
Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert-Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 21, Issue 1

February 2007

272 pages

ISSN:0895-4801

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nannicini G(2024)Fast Quantum Subroutines for the Simplex MethodOperations Research10.1287/opre.2022.234172:2(763-780)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2341
Dumitrescu AMandal RTóth C(2018)Monotone Paths in Geometric TriangulationsTheory of Computing Systems10.5555/3231788.323179862:6(1490-1524)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.5555/3231788.3231798
Eisenbrand FVempala S(2017)Geometric random edgeMathematical Programming: Series A and B10.1007/s10107-016-1089-0164:1-2(325-339)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s10107-016-1089-0
Hansen TZwick UServedio RRubinfeld R(2015)An Improved Version of the Random-Facet Pivoting Rule for the Simplex AlgorithmProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746557(209-218)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746557
Hansen TPaterson MZwick UChekuri C(2014)Improved upper bounds for random-edge and random-jump on abstract cubesProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634139(874-881)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634139
Friedmann OHansen TZwick UFortnow LVadhan S(2011)Subexponential lower bounds for randomized pivoting rules for the simplex algorithmProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993675(283-292)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993675

Abstract

Cited By

Index Terms

Recommendations

Improved upper bounds for random-edge and random-jump on abstract cubes

Lollipop and cubic weight functions for graph pebbling

New Bounds and Constructions for Granular Media Coding

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations