Recent progress on the combinatorial diameter of polytopes and simplicial complexes
From MaRDI portal
Publication:384506
DOI10.1007/s11750-013-0295-7zbMath1280.52011arXiv1307.5900OpenAlexW2050088862MaRDI QIDQ384506
Publication date: 28 November 2013
Published in: Top (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.5900
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial aspects of simplicial complexes (05E45)
Related Items
Diameters of cocircuit graphs of oriented matroids: an update, Improving bounds on the diameter of a polyhedron in high dimensions, The circuit diameter of the Klee-Walkup polyhedron, Hirsch polytopes with exponentially long combinatorial segments, Topological Prismatoids and Small Simplicial Spheres of Large Diameter, The maximum diameter of pure simplicial complexes and pseudo-manifolds, The diameter of type \(D\) associahedra and the non-leaving-face property, Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count, On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes, A refinement of Todd's bound for the diameter of a polyhedron, Monotone paths in geometric triangulations, Randomized construction of complexes with large diameter, An asymptotically improved upper bound on the diameter of polyhedra
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids
- A counterexample to the Hirsch conjecture
- An update on the Hirsch conjecture
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
- A strongly polynomial algorithm for linear systems having a binary solution
- A new polynomial-time algorithm for linear programming
- Nonrealizable minimal vertex triangulations of surfaces: showing nonrealizability using oriented matroids and satisfiability solvers
- Polytopes and arrangements: diameter and curvature
- Triangulations. Structures for algorithms and applications
- A continuous \(d\)-step conjecture for polytopes
- The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes
- On the diameter of convex polytopes
- Upper bounds for the diameter and height of graphs of convex polyhedra
- An upper bound for the diameter of a polytope
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- The Hirsch conjecture is true for (0,1)-polytopes
- The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
- Some upper bounds for the diameters of convex polytopes
- Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- Diameter of Polyhedra: Limits of Abstraction
- Obstructions to weak decomposability for simplicial polytopes
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes
- The d-Step Conjecture and Its Relatives
- Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
- The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- Branched coverings, triangulations, and 3-manifolds
- Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets
- The Hirsch Conjecture Holds for Normal Flag Complexes
- More bounds on the diameters of convex polytopes
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- Paths on Polyhedra. I
- Paths on Polytopes
- Diameters of Polyhedral Graphs
- On sub-determinants and the diameter of polyhedra
- A simple polynomial-time rescaling algorithm for solving linear programs
