The Hirsch conjecture is true for (0,1)-polytopes

DOI10.1007/BF01589099zbMath0684.90071OpenAlexW1985859952WikidataQ59541336 ScholiaQ59541336MaRDI QIDQ1825756

Denis Naddef

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01589099

zbMATH Keywords

diameterhypercubesfacetsadjacencyHamilton connected polytopes

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)

Related Items (41)

Improving bounds on the diameter of a polyhedron in high dimensions ⋮ On the diameter of cut polytopes ⋮ Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ On the diameter of lattice polytopes ⋮ Lattice-free polytopes and their diameter ⋮ Quadratic diameter bounds for dual network flow polyhedra ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Distance between vertices of lattice polytopes ⋮ On the diameter of partition polytopes and vertex-disjoint cycle cover ⋮ Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Circuit walks in integral polyhedra ⋮ On the Number of Solutions Generated by the Simplex Method for LP ⋮ Monotone diameter of bisubmodular polyhedra ⋮ Primitive point packing ⋮ The diameter of lattice zonotopes ⋮ On the Combinatorial Diameters of Parallel and Series Connections ⋮ On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming ⋮ The hierarchy of circuit diameters and transportation polytopes ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ The Hirsch conjecture for the fractional stable set polytope ⋮ Simple 0/1-polytopes ⋮ On sub-determinants and the diameter of polyhedra ⋮ A scaling algorithm for optimizing arbitrary functions over vertices of polytopes ⋮ Constructing Clustering Transformations ⋮ On the diameter of convex polytopes ⋮ Improved bounds on the diameter of lattice polytopes ⋮ On the circuit diameter conjecture ⋮ Geometry, complexity, and combinatorics of permutation polytopes ⋮ Unnamed Item ⋮ The diameters of network-flow polytopes satisfy the Hirsch conjecture ⋮ Primitive zonotopes ⋮ On the shadow simplex method for curved polyhedra ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ A spectral approach to polytope diameter ⋮ Computational determination of the largest lattice polytope diameter ⋮ Elementary moves on lattice polytopes ⋮ An asymptotically improved upper bound on the diameter of polyhedra ⋮ Adjacency on combinatorial polyhedra ⋮ A Generalized Simplex Method for Integer Problems Given by Verification Oracles ⋮ On the Length of Monotone Paths in Polyhedra ⋮ Short simplex paths in lattice polytopes

Cites Work

• Hamiltonicity in (0-1)-polyhedra
• The d-Step Conjecture and Its Relatives

This page was built for publication: The Hirsch conjecture is true for (0,1)-polytopes