Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

On the Simplex Method for 0/1-Polytopes

Published Online:5 Jun 2024https://doi.org/10.1287/moor.2021.0345

References

  • [1] Adler I, Papadimitriou C, Rubinstein A (2014) On simplex pivoting rules and complexity theory. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 8494 (Springer, Cham, Switzerland), 13–24.Crossref, Google Scholar
  • [2] Amenta N, Ziegler GM (2000) Deformed products and maximal shadows of polytopes. Contemporary Math. 223:57–90.Crossref, Google Scholar
  • [3] Avis D, Friedmann O (2017) An exponential lower bound for Cunningham’s rule. Math. Programming 161(1):271–305.Crossref, Google Scholar
  • [4] Beling PA, Megiddo N (1998) Using fast matrix multiplication to find basic solutions. Theoret. Comput. Sci. 205(1):307–316.Crossref, Google Scholar
  • [5] Bertsimas D, Tsitsiklis J (1997) Introduction to Linear Optimization (Athena Scientific, Nashua, NH).Google Scholar
  • [6] Billera LJ, Sturmfels B (1992) Fiber polytopes. Ann. Math. 135(3):527–549.Crossref, Google Scholar
  • [7] Billera LJ, Kapranov M, Sturmfels B (1994) Cellular strings on polytopes. Proc. Amer. Math. Soc. 122(2):549–555.Crossref, Google Scholar
  • [8] Black A, De Loera JA (2023) Monotone paths on cross-polytopes. Discrete Comput. Geometry 70:1245–1265.Crossref, Google Scholar
  • [9] Blanchard M, De Loera JA, Louveaux Q (2021) On the length of monotone paths in polyhedral. SIAM J. Discrete Math. 35(3):1746–1768.Crossref, Google Scholar
  • [10] Borgwardt KH (1977) Untersuchungen zur asymptotik der mittleren schrittzahl von simplexverfahren in der linearen optimierung. PhD thesis, Universität Kaiserslautern, Kaiserslautern, Germany.Google Scholar
  • [11] Borgwardt KH (1987) The Simplex Method: A Probabilistic Analysis, vol. 1, 1st ed. (Springer Science & Business Media, New York).Crossref, Google Scholar
  • [12] Borgwardt S (2013) On the diameter of partition polytopes and vertex-disjoint cycle cover. Math. Programming 141(1):1–20.Crossref, Google Scholar
  • [13] Brunsch T, Röglin H (2013) Finding short paths on polytopes by the shadow vertex algorithm. Fomin FV, Freivalds R, Kwiatkowska M, Peleg D, eds. Automata, Languages, and Programming (Springer, Berlin), 279–290.Crossref, Google Scholar
  • [14] Cardoso DM, Clímaco JCN (1992) The generalized simplex method. Oper. Res. Lett. 12(5):337–348.Crossref, Google Scholar
  • [15] Chubanov S (2021) A generalized simplex method for integer problems given by verification oracles. SIAM J. Optim. 31(1):686–701.Crossref, Google Scholar
  • [16] Chubanov S (2021) A scaling algorithm for optimizing arbitrary functions over vertices of polytopes. Math. Programming 190(1):89–102.Crossref, Google Scholar
  • [17] Chvátal V (1975) On certain polytopes associated with graphs. J. Combinatorial Theory 18(2):138–154.Crossref, Google Scholar
  • [18] Dadush D, Hähnle N (2016) On the shadow simplex method for curved polyhedral. Discrete Comput. Geometry 56(4):882–909.Crossref, Google Scholar
  • [19] Dadush D, Huiberts S (2018) A friendly smoothed analysis of the simplex method. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. STOC 2018 (ACM, New York), 390–403.Google Scholar
  • [20] Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
  • [21] De Loera JA, Hemmecke R, Lee J (2015) On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond. SIAM J. Optim. 25(4):2494–2511.Crossref, Google Scholar
  • [22] De Loera JA, Kafer S, Sanità L (2022) Pivot rules for circuit-augmentation algorithms in linear optimization. SIAM J. Optim. 32(3):2156–2179.Crossref, Google Scholar
  • [23] Del Pia A, Michini C (2022) Short simplex paths in lattice polytopes. Discrete Comput. Geometry 67(2):503–524.Crossref, Google Scholar
  • [24] Dinic EA (1970) Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11:1277–1280.Google Scholar
  • [25] Disser Y, Hopp AV (2019) On Friedmann’s subexponential lower bound for Zadeh’s pivot rule. Lodi A, Nagarajan V, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 168–180.Crossref, Google Scholar
  • [26] Disser Y, Skutella M (2015) The simplex algorithm is NP-mighty. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 858–872.Google Scholar
  • [27] Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2):248–264.Crossref, Google Scholar
  • [28] Eisenbrand F, Vempala S (2017) Geometric random edge. Math. Programming 164(1):325–339.Crossref, Google Scholar
  • [29] Fearnley J, Savani R (2015) The complexity of the simplex method. STOC’15 Proc. 2015 ACM Sympos. Theory Comput. (ACM, New York), 201–208.Google Scholar
  • [30] Forrest JJ, Goldfarb D (1992) Steepest-edge simplex algorithms for linear programming. Math. Programming 57:341–374.Crossref, Google Scholar
  • [31] Friedmann O, Hansen TD, Zwick U (2011) Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. Proc. 43rd ACM Sympos. Theory Comput. STOC’11 (ACM, New York), 283–292.Google Scholar
  • [32] Fulkerson D, Gross O (1965) Incidence matrices and interval graphs. Pacific J. Math. 15(3):835–855.Crossref, Google Scholar
  • [33] Gass S, Saaty T (1955) The computational algorithm for the parametric objective function. Naval Res. Logist. Quart. 2:39–45.Crossref, Google Scholar
  • [34] Goldberg AV, Tarjan RE (1989) Finding minimum-cost circulations by canceling negative cycles. J. ACM 36(4):873–886.Crossref, Google Scholar
  • [35] Goldfarb D (1994) On the complexity of the simplex algorithm. Gomez S, Hennart JP, eds. Adv. Optim. Numer. Anal. Proc. 6th Workshop Optim. Numer. Anal (Kluwer, Dordrecht, Netherlands), 25–38.Google Scholar
  • [36] Goldfarb D, Sit WY (1979) Worst case behavior of the steepest edge simplex method. Discrete Appl. Math. 1(4):277–285.Crossref, Google Scholar
  • [37] Hansen T, Zwick U (2015) An improved version of the random-facet pivoting rule for the simplex algorithm. Proc. Forty-Seventh Annual ACM Sympos. Theory Comput. STOC 2015 (ACM, New York), 209–218.Google Scholar
  • [38] Jones CN, Kerrigan EC, Maciejowski JM (2008) On polyhedral projection and parametric programming. J. Optim. Theory Appl. 138(2):207–220.Crossref, Google Scholar
  • [39] Kitahara T, Mizuno S (2011) A proof by the simplex method for the diameter of a (0, 1)-polytope. Working paper, Tokyo Institute of Technology, Tokyo.Google Scholar
  • [40] Kitahara T, Mizuno S (2011) Klee-Minty’s LP and upper bounds for Dantzig’s simplex method. Oper. Res. Lett. 39(2):88–91.Crossref, Google Scholar
  • [41] Kitahara T, Mizuno S (2013) A bound for the number of different basic solutions generated by the simplex method. Math. Programming 137(1–2):579–586.Crossref, Google Scholar
  • [42] Klee V, Kleinschmidt P (1990) Geometry of the Gass-Saaty parametric cost LP algorithm. Discrete Comput. Geometry 5(1):13–26.Crossref, Google Scholar
  • [43] Klee V, Minty GJ (1972) How good is the simplex algorithm? Proc. Third Sympos. Inequalities, III (Academic Press, New York), 159–175.Google Scholar
  • [44] Kortenkamp U, Richter-Gebert J, Sarangarajan A, Ziegler GM (1997) Extremal properties of 0/1-polytopes. Discrete Comput. Geometry 17(4):439–448.Crossref, Google Scholar
  • [45] Matsui T, Tamura S (1993) Adjacency on combinatorial polyhedra. Discrete Appl. Math. 56:311–321.Crossref, Google Scholar
  • [46] Murty KG (1980) Computational complexity of parametric linear programming. Math. Programming 19(2):213–219.Crossref, Google Scholar
  • [47] Murty KG (1983) Linear Programming (John Wiley & Sons, Inc., New York).Google Scholar
  • [48] Murty KG (2009) Complexity of degeneracy. Floudas CA, Pardalos PM, eds. Encyclopedia of Optimization (Springer US, Boston), 419–425.Google Scholar
  • [49] Naddef D (1989) The Hirsch conjecture is true for (0,1)-polytopes. Math. Programming 45(1):109–110.Crossref, Google Scholar
  • [50] Orlin JB (1997) A polynomial time primal network simplex algorithm for minimum cost flows. Math. Programming 78(2):109–129.Crossref, Google Scholar
  • [51] Rispoli FJ (1992) The monotonic diameter of the perfect matching and shortest path polytopes. Oper. Res. Lett. 12(1):23–27.Crossref, Google Scholar
  • [52] Rispoli FJ (1998) The monotonic diameter of traveling salesman polytopes. Oper. Res. Lett. 22(2–3):69–73.Crossref, Google Scholar
  • [53] Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2):266–283.Crossref, Google Scholar
  • [54] Schrijver A (1986) Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics (John Wiley & Sons Ltd., New York).Google Scholar
  • [55] Schulz AS, Weismantel R, Ziegler GM (1995) 0/1-integer programming: Optimization and augmentation are equivalent. Spirakis P, ed. Algorithms—ESA ‘95 (Springer, Berlin), 473–483.Crossref, Google Scholar
  • [56] Spielman DA, Teng S-H (2006) Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3):385–463.Crossref, Google Scholar
  • [57] Terlaky T (1993) Lexicographic pivoting rules. Floudas CA, Pardalos PM, eds. Encyclopedia of Optimization, 2nd ed. (Springer, Cham, Switzerland), 1870–1873.Google Scholar
  • [58] Terlaky T, Zhang S (1993) Pivot rules for linear programming: A survey on recent theoretical developments. Annals OR 46–47(1):203–233.Crossref, Google Scholar
  • [59] van den Brand J (2021) Unifying matrix data structures: Simplifying and speeding up iterative algorithms. Sympos. Simplicity Algorithms (SOSA) (SIAM, Philadelphia), 1–13.Google Scholar
  • [60] Vanderbei RJ (2008) Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science (Springer, New York).Crossref, Google Scholar
  • [61] Vershynin R (2011) Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput. 39(2):646–678.Crossref, Google Scholar
  • [62] Ye Y (2011) The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Math. Oper. Res. 36(4):593–603.Link, Google Scholar
  • [63] Zadeh N (2010) What is the worst case behavior of the simplex algorithm? Avis D, Bremner D, Deza A, eds. Polyhedral Computation, CRM Proceedings and Lecture Notes, vol. 48 (American Mathematical Society, Providence, RI), 131–143.Google Scholar
  • [64] Ziegler GM (1995) Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (Springer-Verlag, New York).Crossref, Google Scholar
  • [65] Ziegler GM (2000) Lectures on 0/1-polytopes. Polytopes—Combinatorics and Computation, DMV Seminars, vol. 29 (Birkhäuser, Basel, Switzerland), 1–41.Crossref, Google Scholar
  • [66] Ziegler GM (2005) Typical and extremal linear programs. The Sharpest Cut, MPS/SIAM Series on Optimization (SIAM, Philadelphia), 217–230.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree