On the shadow simplex method for curved polyhedra
type: Item
instance of: scholarly article
title: On the shadow simplex method for curved polyhedra
zbMATH Open document ID: 1377.90055
author: Daniel Dadush
author: Nicolai Hähnle
published in: Discrete \& Computational Geometry
publication date: 2016-12-20T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5114/
review text: The shadow simplex has been at the heart of many theoretical attempts to explain the efficiency of the simplex method in practice. This paper deals with the simplex method over polyhedra satisfying certain ``discrete curvature'' lower bounds and the analysis is based on a dual perspective. A new type of dual analysis of the shadow simplex method is developed which provides a clean and powerful tool for improving all previously mentioned results. For linear optimization, given an initial feasible vertex, it is shown that an optimal vertex can be found using an expected \(O(\frac{n^{3}}{\delta} \ln\frac{n}{\delta})\) simplex pivots, each requiring \(O(mn)\) time to compute, where \(m\) is the number of constraints.
reviewed by: Samir Kumar Neogy
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 6666307
zbMATH Keywords: optimization
zbMATH Keywords: linear programming
zbMATH Keywords: simplex method
zbMATH Keywords: diameter of polyhedra
MaRDI profile type: Publication
OpenAlex ID: W2097442471
cites work: The Hirsch Conjecture Holds for Normal Flag Complexes
cites work: The Hirsch Conjecture for Dual Transportation Polyhedra
cites work: An upper bound for the diameter of a polytope
cites work: On sub-determinants and the diameter of polyhedra
cites work: The simplex method. A probabilistic analysis
cites work: A linear bound on the diameter of the transportation polytope
cites work: Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
cites work: Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
cites work: Graphs of transportation polytopes
cites work: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
cites work: Geometric random edge
cites work: Q3974981
cites work: A quasi-polynomial bound for the diameter\\of graphs of polyhedra
cites work: Paths on Polytopes
cites work: The width of five-dimensional prismatoids
cites work: The Hirsch conjecture is true for (0,1)-polytopes
cites work: A counterexample to the Hirsch conjecture
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Smoothed analysis of algorithms
cites work: An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
cites work: Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
DOI: 10.1007/S00454-016-9793-3
description: scientific article; zbMATH DE number 6666307