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

research-article

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

Authors:

Thomas Dueholm Hansen,

Uri ZwickAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 209 - 218

https://doi.org/10.1145/2746539.2746557

Published: 14 June 2015 Publication History

Abstract

The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs (LPs). The expected number of pivoting steps performed by the simplex algorithm when using this rule, on any linear program involving n inequalities in d variables, is 2^{O(√{(n-d),log({d}/{√{n-d}}},)}, where log n=max{1,log n}. A dual version of the algorithm performs an expected number of at most 2^{O(√{d,log({(n-d)}/√d},)} dual pivoting steps. This dual version is currently the fastest known combinatorial algorithm for solving general linear programs. Kalai also obtained a primal pivoting rule which performs an expected number of at most 2^{O(√d,log n)} pivoting steps. We present an improved version of Kalai's pivoting rule for which the expected number of primal pivoting steps is at most min{2^{O(√(n-d),log(d/(n-d)},)},2^{O(√{d,log((n-d)/d}},)}}. This seemingly modest improvement is interesting for at least two reasons. First, the improved bound for the number of primal pivoting steps is better than the previous bounds for both the primal and dual pivoting steps. There is no longer any need to consider a dual version of the algorithm. Second, in the important case in which n=O(d), i.e., the number of linear inequalities is linear in the number of variables, the expected running time becomes 2^O(√d) rather than 2^{O(√d log d)}. Our results, which extend previous results of Gartner, apply not only to LP problems, but also to LP-type problems, supplying in particular slightly improved algorithms for solving 2-player turn-based stochastic games and related problems.

References

[1]

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.

[2]

D. Avis and V. Chvátal. Notes on Bland's pivoting rule. In Polyhedral Combinatorics, volume 8 of Mathematical Programming Studies, pages 24--34. Springer, 1978.

[3]

D. Bertsimas and S. Vempala. Solving convex programs by random walks. J. ACM, 51(4):540--556, 2004.

Digital Library

[4]

H. Björklund and S. Vorobyov. Combinatorial structure and randomized subexponential algorithms for infinite games. Theoretical Computer Science, 349(3):347--360, 2005.

Digital Library

[5]

H. Björklund and S. Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, 155(2):210--229, 2007.

Digital Library

[6]

R. Bland. New finite pivoting rules for the simplex method. Mathematics of Operations Research, 2(2):103--107, 1977.

Digital Library

[7]

V. Chvátal. Linear programming. W. H. Freeman and Company, New York, 1983.

[8]

K. Clarkson. Linear programming in O(n x 3^d2) time. Information Processing Letters, 22(1):21--24, 1986.

Digital Library

[9]

K. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM, 42(2):488--499, 1995.

Digital Library

[10]

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

Digital Library

[11]

G. Dantzig. Linear programming and extensions. Princeton University Press, 1963.

[12]

J. Dunagan and S. Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. Mathematical Programming, 114(1):101--114, 2008.

Digital Library

[13]

M. Dyer. On a multidimensional search technique and its application to the Euclidean one-centre problem. SIAM J. Comput., 15(3):725--738, 1986.

Digital Library

[14]

M. Dyer and A. Frieze. A randomized algorithm for fixed-dimensional linear programming. Mathematical Programming, 44(1--3):203--212, 1989.

Digital Library

[15]

J. Fearnley. Exponential lower bounds for policy iteration. In Proc. of 37th ICALP, pages 551--562, 2010.

Digital Library

[16]

P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

[17]

O. Friedmann. An exponential lower bound for the latest deterministic strategy iteration algorithms. Logical Methods in Computer Science, 7(3), 2011.

[18]

O. Friedmann. A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games. In Proc. of 15th IPCO, pages 192--206, 2011.

Digital Library

[19]

O. Friedmann, T. D. Hansen, and U. Zwick. A subexponential lower bound for the random facet algorithm for parity games. In Proc. of 22nd SODA, pages 202--216, 2011.

Digital Library

[20]

O. Friedmann, T. D. 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

[21]

O. Friedmann, T. D. Hansen, and U. Zwick. Errata for: A subexponential lower bound for the random facet algorithm for parity games. arXiv, arXiv:1410.7871 {cs.DS}, 2014.

[22]

O. Friedmann, T. D. Hansen, and U. Zwick. Random-Facet and Random-Bland require subexponential time even for shortest paths. arXiv, arXiv:1410.7530 {cs.DS}, 2014.

[23]

B. G\"artner. A subexponential algorithm for abstract optimization problems. SIAM Journal on Computing, 24(5):1018--1035, 1995.

Digital Library

[24]

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

Digital Library

[25]

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

Digital Library

[26]

B. G\"artner and I. Schurr. Linear programming and unique sink orientations. In Proc. of 17th SODA, pages 749--757, 2006.

Digital Library

[27]

D. Goldfarb and W. Sit. Worst case behavior of the steepest edge simplex method. Discrete Applied Mathematics, 1(4):277 -- 285, 1979.

[28]

M. Goldwasser. A survey of linear programming in randomized subexponential time. SIGACT News, 26(2):96--104, 1995.

Digital Library

[29]

N. Halman. Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica, 49(1):37--50, 2007.

Digital Library

[30]

T. D. Hansen, P. Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. J. ACM, 60(1):1, 2013.

Digital Library

[31]

T. D. Hansen, M. Paterson, and U. Zwick. Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. In Proc. of 25th SODA, pages 874--881, 2014.

Digital Library

[32]

R. Jeroslow. The simplex algorithm with the pivot rule of maximizing criterion improvement. Discrete Mathematics, 4(4):367--377, 1973.

Digital Library

[33]

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

Digital Library

[34]

G. Kalai. Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete & Computational Geometry, 8:363--372, 1992.

Digital Library

[35]

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

Digital Library

[36]

G. Kalai. Personal communication, 2012.

[37]

G. Kalai and D. Kleitman. Quasi-polynomial bounds for the diameter of graphs and polyhedra. Bull. Amer. Math. Soc., 26:315--316, 1992.

[38]

N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373--395, 1984.

Digital Library

[39]

J. Kelner and D. Spielman. A randomized polynomial-time simplex algorithm for linear programming. In Proc. of 38th STOC, pages 51--60, 2006.

Digital Library

[40]

L. Khachiyan. A polynomial time algorithm in linear programming. Soviet Math. Dokl., 20:191--194, 1979.

[41]

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.

[42]

V. Lifschitz and B. Pittel. The number of increasing subsequences of the random permutation. Journal of Combinatorial Theory, Series A, 31(1):1--20, 1981.

[43]

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

Digital Library

[44]

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

Digital Library

[45]

J. Matou\vsek and B. Gärtner. Understanding and using linear programming. Springer, 2007.

[46]

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

[47]

J. Matou\vsek and T. Szabó. RANDOM EDGE can be exponential on abstract cubes. Advances in Mathematics, 204(1):262--277, 2006.

[48]

N. Megiddo. Linear programming in linear time when the dimension is fixed. J. ACM, 31(1):114--127, 1984.

Digital Library

[49]

M. Puterman. Markov decision processes. Wiley, 1994.

[50]

A. Rasche. On Kalai's survey of linear programming and simple polytopes. Master's thesis, ETH Zürich, 2004.

[51]

F. Santos. A counterexample to the Hirsch conjecture. Annals of mathematics, 176(1):383--412, 2012.

[52]

F. Santos. Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP, 21(3):426--460, 2013.

[53]

A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1986.

Digital Library

[54]

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

[55]

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

Digital Library

[56]

R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423--434, 1991.

Digital Library

[57]

D. Spielman and S. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385--463, 2004.

Digital Library

[58]

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

Digital Library

[59]

M. Todd. An improved Kalai-Kleitman bound for the diameter of a polyhedron. arXiv, arXiv:1402.3579 {math.OC}, 2014.

[60]

U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1--2):343--359, 1996.

Digital Library

Cited By

Bauer PKapfinger JKonrad MLeopold TWilker SSauter T(2024)DER Control: Harnessing DDPG and MILP for Enhanced Performance in Active Energy Management2024 International Workshop on Intelligent Systems (IWIS)10.1109/IWIS62722.2024.10706058(1-6)Online publication date: 28-Aug-2024
https://doi.org/10.1109/IWIS62722.2024.10706058
Kukharenko KSanità L(2024)On the Number of Degenerate Simplex PivotsInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_19(252-264)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-59835-7_19
Huiberts SLee YZhang XSaha BServedio R(2023)Upper and Lower Bounds on the Smoothed Complexity of the Simplex MethodProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585124(1904-1917)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585124
Show More Cited By

Index Terms

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
      2. Generating functions
  2. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming

Recommendations

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No ...
The random facet simplex algorithm on combinatorial cubes
Probabilistic methods in combinatorial optimization

The RANDOM-FACET algorithm is a randomized variant of the simplex method which is known to solve any linear program with n variables and m constraints using an expected number of pivot steps which is subexponential in both n and m. This is the ...
The positive edge pricing rule for the dual simplex

In this paper, we develop the two-dimensional positive edge criterion for the dual simplex. This work extends a similar pricing rule implemented by Towhidi et al. (2014) 24] to reduce the negative effects of degeneracy in the primal simplex. In the dual ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
288
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bauer PKapfinger JKonrad MLeopold TWilker SSauter T(2024)DER Control: Harnessing DDPG and MILP for Enhanced Performance in Active Energy Management2024 International Workshop on Intelligent Systems (IWIS)10.1109/IWIS62722.2024.10706058(1-6)Online publication date: 28-Aug-2024
https://doi.org/10.1109/IWIS62722.2024.10706058
Kukharenko KSanità L(2024)On the Number of Degenerate Simplex PivotsInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_19(252-264)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-59835-7_19
Huiberts SLee YZhang XSaha BServedio R(2023)Upper and Lower Bounds on the Smoothed Complexity of the Simplex MethodProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585124(1904-1917)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585124
Cardinal JSteiner R(2023)Inapproximability of shortest paths on perfect matching polytopesMathematical Programming10.1007/s10107-023-02025-4Online publication date: 21-Oct-2023
https://doi.org/10.1007/s10107-023-02025-4
Cardinal JSteiner R(2023)Inapproximability of Shortest Paths on Perfect Matching PolytopesInteger Programming and Combinatorial Optimization10.1007/978-3-031-32726-1_6(72-86)Online publication date: 22-May-2023
https://doi.org/10.1007/978-3-031-32726-1_6
De Loera JKafer SSanità L(2022)Pivot Rules for Circuit-Augmentation Algorithms in Linear OptimizationSIAM Journal on Optimization10.1137/21M141999432:3(2156-2179)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1419994
Disser YFriedmann OHopp A(2022)An exponential lower bound for Zadeh’s pivot ruleMathematical Programming10.1007/s10107-022-01848-x199:1-2(865-936)Online publication date: 19-Jul-2022
https://doi.org/10.1007/s10107-022-01848-x
Dong SLee YYe GKhuller SVassilevska Williams V(2021)A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central pathProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451056(1784-1797)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451056
Ghate ARyan CSmith R(2021)A Simplex Method for Countably Infinite Linear ProgramsSIAM Journal on Optimization10.1137/19M130393931:4(3157-3183)Online publication date: 13-Dec-2021
https://doi.org/10.1137/19M1303939
Febres G(2019)A Space Decomposition-Based Deterministic Algorithm for Solving Linear Optimization ProblemsAxioms10.3390/axioms80300928:3(92)Online publication date: 1-Aug-2019
https://doi.org/10.3390/axioms8030092
Show More Cited By

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