A spectral approach to polytope diameter

DOI10.1007/s00454-024-00636-yMaRDI QIDQ6642303

Nikhil Srivastava, Rikhav Shah, Hariharan Narayanan

Publication date: 22 November 2024

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

diameterMarkov chainpolytopespectral gap

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A counterexample to the Hirsch conjecture
• The Colin de Verdière number and graphs of polytopes
• On the shadow simplex method for curved polyhedra
• The simplex method. A probabilistic analysis
• The number of faces of a simplicial convex polytope
• An upper bound for the diameter of a polytope
• On simple polytopes
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• The Hirsch conjecture is true for (0,1)-polytopes
• Weights on polytopes
• Absence of mass gap for a class of stochastic contour models.
• A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
• An asymptotically improved upper bound on the diameter of polyhedra
• Geometric random edge
• Zur Theorie der gemischten Volumina von konvexen Körpern. II: Neue Ungleichungen zwischen den gemischten Volumina und ihre Anwendungen.
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Smoothed analysis of algorithms
• Diameters and Eigenvalues
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• An analogue of the Hodge-Riemann relations for simple convex polytopes
• Eigenvalues and the diameter of graphs
• On the expansion of combinatorial polytopes
• A Friendly Smoothed Analysis of the Simplex Method
• Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
• Convex Bodies The Brunn-MinkowskiTheory
• Paths on Polytopes
• On sub-determinants and the diameter of polyhedra

This page was built for publication: A spectral approach to polytope diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6642303)