More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Thomas Dueholm Hansen,

Uri ZwickAuthors Info & Claims

SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

Pages 874 - 881

Published: 05 January 2014 Publication History

Abstract

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 previous upper bound of about 2ⁿ/n^{log n} obtained by Gärtner and Kaibel. For Random-Jump, we obtain an upper bound of about (3/2)ⁿ, improving upon the previous upper bound of about 1.72ⁿ obtained by Mansour and Singh. AUSOs provide an appealing combinatorial abstraction of linear programming and other computational problems such as finding optimal strategies for turn-based Stochastic Games.

References

[1]

I. Adler and R. Saigal. Long monotone paths in abstract polytopes. Mathematics of Operations Research, 1(1): 89--95, 1976.

[2]

N. Amenta and G. Ziegler. Deformed products and maximal shadows of polytopes. In Advances in Discrete and Computational Geometry, pages 57--90, Providence, 1996. Amer. Math. Soc. Contemporary Mathematics 223.

[3]

J. Balogh and R. Pemantle. The Klee-Minty random edge chain moves with linear speed. Random Structures & Algorithms, 30(4): 464--483, 2007.

Digital Library

[4]

A. Condon. The complexity of stochastic games. Information and Computation, 96: 203--224, 1992.

Digital Library

[5]

O. Friedmann, T. Hansen, and U. Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In Proc. of 43th STOC, pages 283--292, 2011.

Digital Library

[6]

B. Gärtner. The random-facet simplex algorithm on combinatorial cubes. Random Structures and Algorithms, 20(3): 353--381, 2002.

Digital Library

[7]

B. Gärtner, M. Henk, and G. Ziegler. Randomized simplex algorithms on Klee-Minty cubes. Combinatorica, 18(3): 349--372, 1998.

[8]

B. Gärtner and V. Kaibel. Two new bounds for the random-edge simplex-algorithm. SIAM J. Discrete Math., 21(1): 178--190, 2007.

Digital Library

[9]

R. Howard. Dynamic programming and Markov processes. MIT Press, 1960.

[10]

G. Kalai. A subexponential randomized simplex algorithm (extended abstract). In Proc. of 24th STOC, pages 475--482, 1992.

Digital Library

[11]

G. Kalai. Linear programming, the simplex algorithm and simple polytopes. Mathematical Programming, 79: 217--233, 1997.

Digital Library

[12]

V. Klee and G. J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalities III, pages 159--175. Academic Press, New York, 1972.

[13]

W. Ludwig. A subexponential randomized algorithm for the simple stochastic game problem. Information and Computation, 117(1): 151--155, 1995.

Digital Library

[14]

Y. Mansour and S. Singh. On the complexity of policy iteration. In Proc. of the 15th UAI, pages 401--408, 1999.

Digital Library

[15]

J. Matoušek. Lower bounds for a subexponential optimization algorithm. Random Structures and Algorithms, 5(4): 591--608, 1994.

Digital Library

[16]

J. Matoušek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16(4--5): 498--516, 1996.

[17]

J. Matoušek and T. Szabó. Random edge can be exponential on abstract cubes. In Proc. of 45th FOCS, pages 92--100, 2004.

Digital Library

[18]

I. Schurr and T. Szabó. Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes. Discrete & Computational Geometry, 31(4): 627--642, 2004.

Digital Library

[19]

I. Schurr and T. Szabó. Jumping doesn't help in abstract cubes. In Proc. of 11th IPCO, pages 225--235, 2005.

Digital Library

[20]

T. Szabó and E. Welzl. Unique sink orientations of cubes. In Proc. of 42th FOCS, pages 547--555, 2001.

Digital Library

[21]

K. Williamson Hoke. Completely unimodal numberings of a simple polytope. Discrete Applied Mathematics, 20(1): 69--81, 1988.

Digital Library

Cited By

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
Fearnley JSavani R(2016)The complexity of all-switches strategy improvementProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884445(130-139)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884445
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

Index Terms

Improved upper bounds for random-edge and random-jump on abstract cubes
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Improved upper bounds on sizes of codes

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as ...
Two New Bounds for the Random-Edge Simplex-Algorithm

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 ...
Upper Bounds on the Size of Obstructions and Intertwines

We give an exponential upper bound inp4on the size of any obstruction for path-width at mostp. We give a doubly exponential upper bound ink5 on the size of any obstruction for tree-width at mostk. We also give an upper bound on the size of any ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms

January 2014

1910 pages

ISBN:9781611973389

Program Chair:
Chandra Chekuri
University of Illinois, Urbana-Champaign

Sponsors

SIAM Activity Group on Discrete Mathematics

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 2014

Check for updates

Qualifiers

Research-article

Conference

SODA '14

Sponsor:

SODA '14: ACM-SIAM Symposium on Discrete Algorithms

January 5 - 7, 2014

Oregon, Portland

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
58
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Fearnley JSavani R(2016)The complexity of all-switches strategy improvementProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884445(130-139)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884445
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

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents