On the shadow simplex method for curved polyhedra
From MaRDI portal
Publication:728496
DOI10.1007/s00454-016-9793-3zbMath1377.90055OpenAlexW2097442471MaRDI QIDQ728496
Publication date: 20 December 2016
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5114/
Related Items (8)
Improving bounds on the diameter of a polyhedron in high dimensions ⋮ On circuit diameter bounds via circuit imbalances ⋮ Enumerative problems for arborescences and monotone paths on polytope graphs ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ An asymptotically improved upper bound on the diameter of polyhedra ⋮ A Generalized Simplex Method for Integer Problems Given by Verification Oracles
Cites Work
- Unnamed Item
- A counterexample to the Hirsch conjecture
- A linear bound on the diameter of the transportation polytope
- Graphs of transportation polytopes
- The simplex method. A probabilistic analysis
- 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
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Geometric random edge
- The Hirsch Conjecture for Dual Transportation Polyhedra
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Smoothed analysis of algorithms
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- The width of five-dimensional prismatoids
- An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
- The Hirsch Conjecture Holds for Normal Flag Complexes
- Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
- Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
- Paths on Polytopes
- On sub-determinants and the diameter of polyhedra
This page was built for publication: On the shadow simplex method for curved polyhedra