Abstract
The Hirsch Conjecture (1957) stated that the graph of a $d$-dimensional polytope with $n$ facets cannot have (combinatorial) diameter greater than $n-d$. That is, any two vertices of the polytope can be connected by a path of at most $n-d$ edges.
This paper presents the first counterexample to the conjecture. Our polytope has dimension $43$ and $86$ facets. It is obtained from a $5$-dimensional polytope with $48$ facets that violates a certain generalization of the $d$-step conjecture of Klee and Walkup.
-
[Barnette]
D. Barnette, "$W_{v}$ paths on 3-polytopes," J. Combinatorial Theory, vol. 7, pp. 62-70, 1969.@article {Barnette, MRKEY = {0248636},
AUTHOR = {Barnette, David},
TITLE = {{$W\sb{v}$} paths on 3-polytopes},
JOURNAL = {J. Combinatorial Theory},
VOLUME = {7},
YEAR = {1969},
PAGES = {62--70},
MRCLASS = {52.10},
MRNUMBER = {0248636},
MRREVIEWER = {G. D. Chakerian},
ZBLNUMBER = {0177.26804},
DOI = {10.1016/S0021-9800(69)80007-4},
} -
[Barnette-LBT] D. Barnette, "A proof of the lower bound conjecture for convex polytopes," Pacific J. Math., vol. 46, pp. 349-354, 1973.
@article {Barnette-LBT, MRKEY = {0328773},
AUTHOR = {Barnette, David},
TITLE = {A proof of the lower bound conjecture for convex polytopes},
JOURNAL = {Pacific J. Math.},
FJOURNAL = {Pacific Journal of Mathematics},
VOLUME = {46},
YEAR = {1973},
PAGES = {349--354},
ISSN = {0030-8730},
MRCLASS = {52A25},
MRNUMBER = {0328773},
MRREVIEWER = {E. Jucovic},
ZBLNUMBER = {0264.52006},
URL = {http://projecteuclid.org/euclid.pjm/1102946311},
} -
[Barnette2] D. Barnette, "An upper bound for the diameter of a polytope," Discrete Math., vol. 10, pp. 9-13, 1974.
@article {Barnette2, MRKEY = {0355826},
AUTHOR = {Barnette, David},
TITLE = {An upper bound for the diameter of a polytope},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {10},
YEAR = {1974},
PAGES = {9--13},
ISSN = {0012-365X},
MRCLASS = {52A25},
MRNUMBER = {0355826},
MRREVIEWER = {P. McMullen},
ZBLNUMBER = {0294.52007},
DOI = {10.1016/0012-365X(74)90016-8},
} -
[BlindBlind] G. Blind and R. Blind, "The cubical $d$-polytopes with fewer than $2^{d+1}$ vertices," Discrete Comput. Geom., vol. 13, iss. 3-4, pp. 321-345, 1995.
@article {BlindBlind, MRKEY = {1318781},
AUTHOR = {Blind, G. and Blind, R.},
TITLE = {The cubical {$d$}-polytopes with fewer than {$2\sp {d+1}$} vertices},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {13},
YEAR = {1995},
NUMBER = {3-4},
PAGES = {321--345},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {52B05},
MRNUMBER = {1318781},
MRREVIEWER = {Margaret M. Bayer},
DOI = {10.1007/BF02574048},
ZBLNUMBER = {0824.52013},
} -
[BCSS] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, New York: Springer-Verlag, 1998.
@book {BCSS, MRKEY = {1479636},
AUTHOR = {Blum, Lenore and Cucker, Felipe and Shub, Michael and Smale, Steve},
TITLE = {Complexity and Real Computation},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1998},
PAGES = {xvi+453},
ISBN = {0-387-98281-7},
MRCLASS = {68Q15 (03D15 13P99 14P99 65Y20 68-02)},
MRNUMBER = {1479636},
MRREVIEWER = {Klaus Meer},
ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
ZBLNUMBER = {0948.68068},
ZBLNUMBER = {0872.68036},
} -
[BSS] L. Blum, M. Shub, and S. Smale, "On a theory of computation and complexity over the real numbers: ${NP}$-completeness, recursive functions and universal machines," Bull. Amer. Math. Soc., vol. 21, iss. 1, pp. 1-46, 1989.
@article {BSS, MRKEY = {0974426},
AUTHOR = {Blum, Lenore and Shub, Mike and Smale, Steve},
TITLE = {On a theory of computation and complexity over the real numbers: ${NP}$-completeness, recursive functions and universal machines},
JOURNAL = {Bull. Amer. Math. Soc.},
FJOURNAL = {American Mathematical Society. Bulletin. New Series},
VOLUME = {21},
YEAR = {1989},
NUMBER = {1},
PAGES = {1--46},
ISSN = {0273-0979},
CODEN = {BAMOAD},
MRCLASS = {68Q10 (03D15 03D75 03D80 03F60 68Q15 68Q25)},
MRNUMBER = {0974426},
MRREVIEWER = {John Michael Robson},
DOI = {10.1090/S0273-0979-1989-15750-9},
ZBLNUMBER = {0681.03020},
} -
[Borgwardt-book] K. Borgwardt, The Simplex Method. A Probabilistic Analysis, New York: Springer-Verlag, 1987, vol. 1.
@book {Borgwardt-book, MRKEY = {0868467},
AUTHOR = {Borgwardt, Karl-Heinz},
TITLE = {The Simplex Method. A Probabilistic Analysis},
SERIES = {Algorithms and Combin.},
VOLUME = {1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1987},
PAGES = {xii+268},
ISBN = {3-540-17096-0},
MRCLASS = {90C05},
MRNUMBER = {0868467},
MRREVIEWER = {J{ü}rgen K{ö}hler},
ZBLNUMBER = {0604.90092},
} -
[Bremner:MoreBounds] D. Bremner, A. Deza, W. Hua, and L. Schewe, More bounds on the diameter of convex polytopes, 2009.
@misc {Bremner:MoreBounds,
author={Bremner, David and Deza, A. and Hua, W. and Schewe, L.},
TITLE={More bounds on the diameter of convex polytopes},
NOTE={{\it Optimization Methods and Software},
to appear},
DOI={10.1080/10556788.2012.668906},
ARXIV={0911.4982},
YEAR={2009},
} -
[Bremner:DiameterFewFacets] D. Bremner and L. Schewe, "Edge-graph diameter bounds for convex polytopes with few facets," Exp. Math., vol. 20, iss. 3, pp. 229-237, 2011.
@article {Bremner:DiameterFewFacets, MRKEY = {2836249},
AUTHOR = {Bremner, David and Schewe, Lars},
TITLE = {Edge-graph diameter bounds for convex polytopes with few facets},
JOURNAL = {Exp. Math.},
FJOURNAL = {Experimental Mathematics},
VOLUME = {20},
YEAR = {2011},
NUMBER = {3},
PAGES = {229--237},
ISSN = {1058-6458},
MRCLASS = {52B05 (05B35 52B40)},
MRNUMBER = {2836249},
DOI = {10.1080/10586458.2011.564965},
} -
[Dantzig-simplex] G. B. Dantzig, "Maximization of a linear function of variables subject to linear inequalities," in Activity Analysis of Production and Allocation, New York, N. Y.: John Wiley & Sons, 1951, vol. 13, pp. 339-347.
@incollection {Dantzig-simplex, MRKEY = {0056260},
AUTHOR = {Dantzig, George B.},
TITLE = {Maximization of a linear function of variables subject to linear inequalities},
BOOKTITLE = {Activity {A}nalysis of {P}roduction and {A}llocation},
SERIES = {Cowles Commission Monogr.},
VOLUME={13},
PAGES = {339--347},
PUBLISHER = {John Wiley \& Sons},
ADDRESS = {New York, N. Y.},
YEAR = {1951},
MRCLASS = {90.0X},
MRNUMBER = {0056260},
MRREVIEWER = {H. W. Kuhn},
ZBLNUMBER = {0045.09802},
} -
[Dantzig-book] G. B. Dantzig, Linear Programming and Extensions, Princeton, NJ: Princeton Univ. Press, 1998.
@book {Dantzig-book, MRKEY = {1658673},
AUTHOR = {Dantzig, George B.},
TITLE = {Linear Programming and Extensions},
SERIES = {Princeton Landmarks in Math.},
PUBLISHER = {Princeton Univ. Press},
ADDRESS = {Princeton, NJ},
YEAR = {1998},
PAGES = {xviii+627},
ISBN = {0-691-05913-6},
MRCLASS = {90-01 (90-02 90C05)},
MRNUMBER = {1658673},
ZBLNUMBER = {0997.90504},
} -
[triang-book] J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures for Algorithms and Applications, New York: Springer-Verlag, 2010, vol. 25.
@book {triang-book, MRKEY = {2743368},
AUTHOR = {De Loera, Jes{ú}s A. and Rambau, J{ö}rg and Santos, Francisco},
TITLE = {Triangulations: Structures for Algorithms and Applications},
SERIES = {Algorithms Comput. Math.},
VOLUME = {25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2010},
PAGES = {xiv+535},
ISBN = {978-3-642-12970-4},
MRCLASS = {52B55 (05C10 52B05 57Q15 68U05)},
MRNUMBER = {2743368},
ZBLNUMBER = {1207.52002},
} -
[Dongarra-Sullivan-topten] J. Dongarra and F. Sullivan, "Guest Editors’ Introduction: The Top 10 Algorithms," Comput. Sci. Eng., vol. 2, pp. 22-23, 2000.
@article{Dongarra-Sullivan-topten,
author={Dongarra, J. and Sullivan, F.},
TITLE={Guest Editors' Introduction: {T}he Top 10 Algorithms},
JOURNAL={Comput.~Sci.~Eng.},
VOLUME={2},
YEAR={2000},
PAGES={22--23},
DOI = {10.1109/MCISE.2000.814652},
} -
[Eisenbrand:limits-of-abstraction] F. Eisenbrand, N. Hähnle, A. Razborov, and T. Rothvoß, "Diameter of polyhedra: limits of abstraction," Math. Oper. Res., vol. 35, iss. 4, pp. 786-794, 2010.
@article {Eisenbrand:limits-of-abstraction, MRKEY = {2777514},
AUTHOR = {Eisenbrand, Friedrich and H{ä}hnle, Nicolai and Razborov, Alexander and Rothvoß,
Thomas},
TITLE = {Diameter of polyhedra: limits of abstraction},
JOURNAL = {Math. Oper. Res.},
FJOURNAL = {Mathematics of Operations Research},
VOLUME = {35},
YEAR = {2010},
NUMBER = {4},
PAGES = {786--794},
ISSN = {0364-765X},
MRCLASS = {52B05 (05B40 05C12 05C90)},
MRNUMBER = {2777514},
MRREVIEWER = {Ren Ding},
DOI = {10.1287/moor.1100.0470},
ZBLNUMBER = {1226.52004},
} -
[Fogel-Halperin-Weibel] E. Fogel, D. Halperin, and C. Weibel, "On the exact maximum complexity of Minkowski sums of polytopes," Discrete Comput. Geom., vol. 42, iss. 4, pp. 654-669, 2009.
@article {Fogel-Halperin-Weibel, MRKEY = {2556461},
AUTHOR = {Fogel, Efi and Halperin, Dan and Weibel, Christophe},
TITLE = {On the exact maximum complexity of {M}inkowski sums of polytopes},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {42},
YEAR = {2009},
NUMBER = {4},
PAGES = {654--669},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {52C45},
MRNUMBER = {2556461},
MRREVIEWER = {M{á}rton Nasz{ó}di},
DOI = {10.1007/s00454-009-9159-1},
ZBLNUMBER = {1207.52012},
} -
[Friedman] O. Friedmann, "A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games," in Integer Programming and Combinatorial Optimization, 15th International Conference, New York, 2011, pp. 192-206.
@inproceedings{Friedman,
author={Friedmann, O.},
TITLE={A subexponential lower bound for {Z}adeh's pivoting rule for solving linear programs and games},
BOOKTITLE={Integer Programming and Combinatorial Optimization, 15th International Conference},
VENUE={IPCO 2011, New York, NY},
SERIES={Lect. Notes Comp. Sci.},
VOLUME={6655},
PUBLISHER={Springer-Verlag},
ADDRESS={New York},
YEAR={2011},
PAGES={192--206},
DOI = {10.1007/978-3-642-20807-2_16},
} -
[Friedman-Hansen-Zwick] O. Friedmann, T. Hansen, and U. Zwick, "Subexponential lower bounds for randomized pivoting rules for the simplex algorithm," in STOC ’11:Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, New York, 2011, pp. 283-292.
@inproceedings{Friedman-Hansen-Zwick,
author={Friedmann, O. and Hansen, T. and Zwick, U.},
TITLE={Subexponential lower bounds for randomized pivoting rules for the simplex algorithm},
BOOKTITLE={STOC '11:Proceedings of the 43rd Annual ACM Symposium on Theory of Computing},
VENUE={San Jose, California},
PUBLISHER={ACM},
ADDRESS={New York},
YEAR={2011},
PAGES={283--292},
DOI = {10.1145/1993636.1993675},
} -
[polymake] E. Gawrilow and M. Joswig, "Polymake: a framework for analyzing convex polytopes," in Polytopes—Combinatorics and Computation, Basel: Birkhäuser, 2000, vol. 29, pp. 43-73.
@incollection {polymake, MRKEY = {1785292},
AUTHOR = {Gawrilow, Ewgenij and Joswig, Michael},
TITLE = {Polymake: a framework for analyzing convex polytopes},
BOOKTITLE = {Polytopes---Combinatorics and Computation},
VENUE={{O}berwolfach, 1997},
SERIES = {DMV Sem.},
VOLUME = {29},
PAGES = {43--73},
PUBLISHER = {Birkhäuser},
ADDRESS = {Basel},
YEAR = {2000},
MRCLASS = {52B55 (68U05)},
MRNUMBER = {1785292},
ZBLNUMBER = {0960.68182},
} -
[GritzmannKlee] P. Gritzmann and V. Klee, "Mathematical programming and convex geometry," in Handbook of Convex Geometry, Vol. A, B, Amsterdam: North-Holland, 1993, pp. 627-674.
@incollection {GritzmannKlee, MRKEY = {1242992},
AUTHOR = {Gritzmann, Peter and Klee, Victor},
TITLE = {Mathematical programming and convex geometry},
BOOKTITLE = {Handbook of Convex Geometry, {V}ol. {A},
{B}},
PAGES = {627--674},
PUBLISHER = {North-Holland},
ADDRESS = {Amsterdam},
YEAR = {1993},
MRCLASS = {52A41 (90C05 90C25)},
MRNUMBER = {1242992},
MRREVIEWER = {Mark E. Hartmann},
ZBLNUMBER = {0806.90098},
} -
[Grunbaum-book] B. Grünbaum, Convex Polytopes, Second ed., New York: Springer-Verlag, 2003, vol. 221.
@book {Grunbaum-book, MRKEY = {1976856},
AUTHOR = {Gr{ü}nbaum, Branko},
TITLE = {Convex Polytopes},
SERIES = {Grad. Texts in Math.},
VOLUME = {221},
EDITION = {Second},
NOTE = {prepared and with a preface by Volker Kaibel, Victor Klee and G{ü}nter M. Ziegler},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2003},
PAGES = {xvi+468},
ISBN = {0-387-00424-6; 0-387-40409-0},
MRCLASS = {52-01 (52Bxx)},
MRNUMBER = {1976856},
MRREVIEWER = {Alexander Zvonkin},
ZBLNUMBER = {1024.52001},
} -
[Khachiyan] L. G. Havcijan, "A polynomial algorithm in linear programming," Dokl. Akad. Nauk SSSR, vol. 244, iss. 5, pp. 1093-1096, 1979.
@article {Khachiyan, MRKEY = {0522052},
AUTHOR = {Ha{\v{c}}ijan, L. G.},
TITLE = {A polynomial algorithm in linear programming},
JOURNAL = {Dokl. Akad. Nauk SSSR},
FJOURNAL = {Doklady Akademii Nauk SSSR},
VOLUME = {244},
YEAR = {1979},
NUMBER = {5},
PAGES = {1093--1096},
ISSN = {0002-3264},
MRCLASS = {90C05},
MRNUMBER = {0522052},
MRREVIEWER = {M. Stef{\u{a}}nescu},
ZBLNUMBER = {0414.90086},
} -
[Hahnle:polymath3] N. Hähnle, Post in G.~Kalai, Polymath 3: Polynomial Hirsch Conjecture, 2010.
@misc{Hahnle:polymath3,
author={Hähnle, N.},
TITLE={post in {G}.~{K}alai, \textit{{P}olymath} {\bf 3}: {P}olynomial {H}irsch {C}onjecture},
YEAR={2010},
URL = {http://gilkalai.wordpress.com/2010/09/29/polymath-3-polynomial-hirsch-conjecture/},
} -
[Holt:Many-polytopes] F. B. Holt and V. Klee, "Many polytopes meeting the conjectured Hirsch bound," Discrete Comput. Geom., vol. 20, iss. 1, pp. 1-17, 1998.
@article {Holt:Many-polytopes, MRKEY = {1626691},
AUTHOR = {Holt, F. B. and Klee, V.},
TITLE = {Many polytopes meeting the conjectured {H}irsch bound},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {20},
YEAR = {1998},
NUMBER = {1},
PAGES = {1--17},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {52B05 (52B11)},
MRNUMBER = {1626691},
MRREVIEWER = {P. R. Goodey},
DOI = {10.1007/PL00009372},
ZBLNUMBER = {0926.52013},
} -
[JoswigZiegler] M. Joswig and G. M. Ziegler, "Neighborly cubical polytopes," Discrete Comput. Geom., vol. 24, iss. 2-3, pp. 325-344, 2000.
@article {JoswigZiegler, MRKEY = {1758054},
AUTHOR = {Joswig, M. and Ziegler, G. M.},
TITLE = {Neighborly cubical polytopes},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {24},
YEAR = {2000},
NUMBER = {2-3},
PAGES = {325--344},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {52B05 (52B40)},
MRNUMBER = {1758054},
DOI = {10.1007/s004540010039},
ZBLNUMBER = {1066.52012},
} -
[Kalai:Quasi-polynomial] G. Kalai and D. J. Kleitman, "A quasi-polynomial bound for the diameter of graphs of polyhedra," Bull. Amer. Math. Soc., vol. 26, iss. 2, pp. 315-316, 1992.
@article {Kalai:Quasi-polynomial, MRKEY = {1130448},
AUTHOR = {Kalai, Gil and Kleitman, Daniel J.},
TITLE = {A quasi-polynomial bound for the diameter of graphs of polyhedra},
JOURNAL = {Bull. Amer. Math. Soc.},
FJOURNAL = {American Mathematical Society. Bulletin. New Series},
VOLUME = {26},
YEAR = {1992},
NUMBER = {2},
PAGES = {315--316},
ISSN = {0273-0979},
CODEN = {BAMOAD},
MRCLASS = {52B55},
MRNUMBER = {1130448},
MRREVIEWER = {W. J. Firey},
DOI = {10.1090/S0273-0979-1992-00285-9},
ZBLNUMBER = {0751.52006},
} -
[Karmarkar] N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica, vol. 4, iss. 4, pp. 373-395, 1984.
@article {Karmarkar, MRKEY = {0779900},
AUTHOR = {Karmarkar, N.},
TITLE = {A new polynomial-time algorithm for linear programming},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
VOLUME = {4},
YEAR = {1984},
NUMBER = {4},
PAGES = {373--395},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {90C05},
MRNUMBER = {0779900},
MRREVIEWER = {K. G. Murty},
DOI = {10.1007/BF02579150},
ZBLNUMBER = {0557.90065},
} -
[Kim-Santos-update] E. D. Kim and F. Santos, "An update on the Hirsch conjecture," Jahresber. Dtsch. Math.-Ver., vol. 112, iss. 2, pp. 73-98, 2010.
@article {Kim-Santos-update, MRKEY = {2681516},
AUTHOR = {Kim, Edward D. and Santos, Francisco},
TITLE = {An update on the {H}irsch conjecture},
JOURNAL = {Jahresber. Dtsch. Math.-Ver.},
FJOURNAL = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
VOLUME = {112},
YEAR = {2010},
NUMBER = {2},
PAGES = {73--98},
ISSN = {0012-0456},
MRCLASS = {52B05 (05C10 05C12 90C08)},
MRNUMBER = {2681516},
DOI = {10.1365/s13291-010-0001-8},
ZBLNUMBER = {05827607},
} -
[Kim-Santos-companion] E. D. Kim and F. Santos, Companion to “An update on the Hirsch conjecture".
@misc {Kim-Santos-companion,
author = {Kim, Edward D. and Santos, Francisco},
TITLE = {Companion to ``{A}n update on the {H}irsch conjecture"},
NOTE={unpublished manuscript, 22 pages, February 2010},
SORTYEAR={2012},
ARXIV={0912.4235v2},
} -
[Klee:diameters] V. Klee, "Diameters of polyhedral graphs," Canad. J. Math., vol. 16, pp. 602-614, 1964.
@article {Klee:diameters, MRKEY = {0165514},
AUTHOR = {Klee, Victor},
TITLE = {Diameters of polyhedral graphs},
JOURNAL = {Canad. J. Math.},
FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
VOLUME = {16},
YEAR = {1964},
PAGES = {602--614},
ISSN = {0008-414X},
MRCLASS = {55.10 (52.10)},
MRNUMBER = {0165514},
MRREVIEWER = {W. T. Tutte},
ZBLNUMBER = {0121.37701},
DOI = {10.4153/CJM-1964-061-2},
} -
[Klee:number-of-vertices] V. Klee, "On the number of vertices of a convex polytope," Canad. J. Math., vol. 16, pp. 701-720, 1964.
@article {Klee:number-of-vertices, MRKEY = {0166682},
AUTHOR = {Klee, Victor},
TITLE = {On the number of vertices of a convex polytope},
JOURNAL = {Canad. J. Math.},
FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
VOLUME = {16},
YEAR = {1964},
PAGES = {701--720},
ISSN = {0008-414X},
MRCLASS = {52.10 (52.40)},
MRNUMBER = {0166682},
MRREVIEWER = {G. D. Chakerian},
ZBLNUMBER = {0128.17201},
DOI = {/10.4153/CJM-1964-067-6}
} -
[Klee:PathsII] V. Klee, "Paths on polyhedra. II," Pacific J. Math., vol. 17, pp. 249-262, 1966.
@article {Klee:PathsII, MRKEY = {0194982},
AUTHOR = {Klee, Victor},
TITLE = {Paths on polyhedra. {II}},
JOURNAL = {Pacific J. Math.},
FJOURNAL = {Pacific Journal of Mathematics},
VOLUME = {17},
YEAR = {1966},
PAGES = {249--262},
ISSN = {0030-8730},
MRCLASS = {52.10},
MRNUMBER = {0194982},
MRREVIEWER = {G. D. Chakerian},
ZBLNUMBER = {0141.21303},
URL = {http://projecteuclid.org/euclid.pjm/1102994619},
} -
[Klee-grunbaumchapter] V. Klee, Diameters of polytopes, 1967.
@misc{Klee-grunbaumchapter,
author={Klee, Victor},
TITLE={Diameters of polytopes},
YEAR={1967},
NOTE={Chapter 16 of~\cite{Grunbaum-book}},
MRNUMBER = {1976856},
ZBLNUMBER = {1024.52001},
} -
[Klee-Kleinschmidt] V. Klee and P. Kleinschmidt, "The $d$-step conjecture and its relatives," Math. Oper. Res., vol. 12, iss. 4, pp. 718-755, 1987.
@article {Klee-Kleinschmidt, MRKEY = {0913867},
AUTHOR = {Klee, Victor and Kleinschmidt, Peter},
TITLE = {The {$d$}-step conjecture and its relatives},
JOURNAL = {Math. Oper. Res.},
FJOURNAL = {Mathematics of Operations Research},
VOLUME = {12},
YEAR = {1987},
NUMBER = {4},
PAGES = {718--755},
ISSN = {0364-765X},
MRCLASS = {52A25 (52A40 90C10)},
MRNUMBER = {0913867},
MRREVIEWER = {G. Ewald},
DOI = {10.1287/moor.12.4.718},
ZBLNUMBER = {0632.52007},
} -
[Klee:d-step] V. Klee and D. W. Walkup, "The $d$-step conjecture for polyhedra of dimension $d<6$," Acta Math., vol. 117, pp. 53-78, 1967.
@article {Klee:d-step, MRKEY = {0206823},
AUTHOR = {Klee, Victor and Walkup, David W.},
TITLE = {The {$d$}-step conjecture for polyhedra of dimension {$d<6$}},
JOURNAL = {Acta Math.},
FJOURNAL = {Acta Mathematica},
VOLUME = {117},
YEAR = {1967},
PAGES = {53--78},
ISSN = {0001-5962},
MRCLASS = {52.40 (52.10)},
MRNUMBER = {0206823},
MRREVIEWER = {G. T. Sallee},
ZBLNUMBER = {0163.16801},
DOI = {10.1007/BF02395040},
} -
[Larman] D. G. Larman, "Paths of polytopes," Proc. London Math. Soc., vol. 20, pp. 161-178, 1970.
@article {Larman, MRKEY = {0254735},
AUTHOR = {Larman, D. G.},
TITLE = {Paths of polytopes},
JOURNAL = {Proc. London Math. Soc.},
FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
VOLUME = {20},
YEAR = {1970},
PAGES = {161--178},
ISSN = {0024-6115},
MRCLASS = {52.10},
MRNUMBER = {0254735},
MRREVIEWER = {P. McMullen},
ZBLNUMBER = {0199.59301},
DOI = {10.1112/plms/s3-20.1.161},
} -
[5prismatoids] B. Matschke, F. Santos, and C. Weibel, The width of 5-prismatoids, 2012.
@misc{5prismatoids,
author={Matschke, B. and Santos, F. and Weibel, C.},
TITLE={The width of 5-prismatoids},
NOTE={preprint},
YEAR={2012},
ARXIV={1202.4701},
} -
[Megiddo:SurveyLPComplexity] N. Megiddo, "On the complexity of linear programming," in Advances in Economic Theory, Cambridge: Cambridge Univ. Press, 1989, vol. 12, pp. 225-268.
@incollection {Megiddo:SurveyLPComplexity, MRKEY = {1117042},
AUTHOR = {Megiddo, Nimrod},
TITLE = {On the complexity of linear programming},
BOOKTITLE = {Advances in Economic Theory},
VENUE={{C}ambridge, {MA},
1985},
SERIES = {Econom. Soc. Monogr.},
VOLUME = {12},
PAGES = {225--268},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {1989},
MRCLASS = {90C05 (90C60)},
MRNUMBER = {1117042},
ZBLNUMBER = {0735.90044},
} -
[ProvanBillera] S. J. Provan and L. J. Billera, "Decompositions of simplicial complexes related to diameters of convex polyhedra," Math. Oper. Res., vol. 5, iss. 4, pp. 576-594, 1980.
@article {ProvanBillera, MRKEY = {0593648},
AUTHOR = {Provan, J. Scott and Billera, Louis J.},
TITLE = {Decompositions of simplicial complexes related to diameters of convex polyhedra},
JOURNAL = {Math. Oper. Res.},
FJOURNAL = {Mathematics of Operations Research},
VOLUME = {5},
YEAR = {1980},
NUMBER = {4},
PAGES = {576--594},
ISSN = {0364-765X},
MRCLASS = {52A25 (90C05)},
MRNUMBER = {0593648},
MRREVIEWER = {J. Parida},
DOI = {10.1287/moor.5.4.576},
ZBLNUMBER = {0457.52005},
} -
[4prismatoids] F. Santos, T. Stephen, and H. Thomas, "Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids," Discrete Comput. Geom., vol. 47, iss. 3, pp. 569-576, 2012.
@article {4prismatoids,
author = {Santos, Francisco and Stephen, Tamon and Thomas, Hugh},
TITLE = {Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {47},
YEAR = {2012},
NUMBER = {3},
PAGES = {569--576},
ISSN = {0179-5376},
CODEN = {DCGEER},
MRCLASS = {Preliminary Data},
DOI = {10.1007/s00454-011-9361-9},
ZBLNUMBER = {06021994},
} -
[Smale] S. Smale, "Mathematical problems for the next century," in Mathematics: Frontiers and Perspectives, Providence, RI: Amer. Math. Soc., 2000, pp. 271-294.
@incollection {Smale, MRKEY = {1754783},
AUTHOR = {Smale, Steve},
TITLE = {Mathematical problems for the next century},
BOOKTITLE = {Mathematics: Frontiers and Perspectives},
PAGES = {271--294},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
YEAR = {2000},
MRCLASS = {00A05 (00-02 01A61 01A67)},
MRNUMBER = {1754783},
ZBLNUMBER = {1031.00005},
} -
[Spielman:WhySimplexUsually] D. A. Spielman and S. Teng, "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time," J. ACM, vol. 51, iss. 3, pp. 385-463, 2004.
@article {Spielman:WhySimplexUsually, MRKEY = {2145860},
AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
TITLE = {Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time},
JOURNAL = {J. ACM},
FJOURNAL = {Journal of the ACM},
VOLUME = {51},
YEAR = {2004},
NUMBER = {3},
PAGES = {385--463},
ISSN = {0004-5411},
MRCLASS = {90C05 (68W40 90C60)},
MRNUMBER = {2145860},
MRREVIEWER = {Panos M. Pardalos},
DOI = {10.1145/990308.990310},
ZBLNUMBER = {1192.90120},
} -
[Terlaky-Zhang] T. Terlaky and S. Z. Zhang, "Pivot rules for linear programming: A survey on recent theoretical developments. Degeneracy in optimization problems," Ann. Oper. Res., vol. 46/47, iss. 1-4, pp. 203-233, 1993.
@article {Terlaky-Zhang, MRKEY = {1260019},
AUTHOR = {Terlaky, Tam{á}s and Zhang, Shu Zhong},
TITLE = {Pivot rules for linear programming: A survey on recent theoretical developments. Degeneracy in optimization problems},
JOURNAL = {Ann. Oper. Res.},
FJOURNAL = {Annals of Operations Research},
VOLUME = {46/47},
YEAR = {1993},
NUMBER = {1-4},
PAGES = {203--233},
ISSN = {0254-5330},
MRCLASS = {90C05 (90-02)},
MRNUMBER = {1260019},
DOI = {10.1007/BF02096264},
ZBLNUMBER = {0793.90034},
} -
[Todd:MonotonicBoundedHirsch] M. J. Todd, "The monotonic bounded Hirsch conjecture is false for dimension at least $4$," Math. Oper. Res., vol. 5, iss. 4, pp. 599-601, 1980.
@article {Todd:MonotonicBoundedHirsch, MRKEY = {0593650},
AUTHOR = {Todd, Michael J.},
TITLE = {The monotonic bounded {H}irsch conjecture is false for dimension at least {$4$}},
JOURNAL = {Math. Oper. Res.},
FJOURNAL = {Mathematics of Operations Research},
VOLUME = {5},
YEAR = {1980},
NUMBER = {4},
PAGES = {599--601},
ISSN = {0364-765X},
MRCLASS = {52A25 (90C05)},
MRNUMBER = {0593650},
MRREVIEWER = {J. Parida},
DOI = {10.1287/moor.5.4.599},
ZBLNUMBER = {0457.52006},
} -
[Todd:Dantzig] M. J. Todd, "Book review on “The basic George B. Dantzig” (by Richard W.~Cottle, Stanford University Press, Stanford, California, 2003)," Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 123-129, 2011.
@article {Todd:Dantzig, MRKEY = {2731656},
AUTHOR = {Todd, Michael J.},
TITLE = {book review on ``{T}he basic {G}eorge {B}. {D}antzig'' (by {R}ichard {W}.~{C}ottle, {S}tanford {U}niversity {P}ress, {S}tanford, {C}alifornia, 2003)},
JOURNAL = {Bull. Amer. Math. Soc.},
FJOURNAL = {American Mathematical Society. Bulletin. New Series},
VOLUME = {48},
YEAR = {2011},
NUMBER = {1},
PAGES = {123--129},
ISSN = {0273-0979},
CODEN = {BAMOAD},
MRCLASS = {00A17},
MRNUMBER = {2731656},
DOI = {10.1090/S0273-0979-2010-01303-3},
} -
[Ziegler:LecturesPolytopes] G. M. Ziegler, Lectures on Polytopes, New York: Springer-Verlag, 1995, vol. 152.
@book {Ziegler:LecturesPolytopes, MRKEY = {1311028},
AUTHOR = {Ziegler, G{ü}nter M.},
TITLE = {Lectures on Polytopes},
SERIES = {Grad. Texts in Math.},
VOLUME = {152},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {1995},
PAGES = {x+370},
ISBN = {0-387-94365-X},
MRCLASS = {52Bxx},
MRNUMBER = {1311028},
MRREVIEWER = {Margaret M. Bayer},
ZBLNUMBER = {0823.52002},
}
Full Article