On the shadow simplex method for curved polyhedra

DOI10.1007/s00454-016-9793-3zbMath1377.90055OpenAlexW2097442471MaRDI QIDQ728496

Nicolai Hähnle, Daniel Dadush

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/

zbMATH Keywords

optimizationlinear programmingsimplex methoddiameter of polyhedra

Mathematics Subject Classification ID

Linear programming (90C05)

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