On the circuit diameter of some combinatorial polytopes

DOI10.1137/17M1152115MaRDI QIDQ4644426zbMATH OpenFDO

Authors Sean Kafer, Kanstantsin Pashkovich, Laura Sanità

Publication date 7 January 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.09642

zbMATH Keywords

circuit diametercombinatorial diameterfractional stable set polytopematching polytopepolytopestraveling salesman polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: The combinatorial diameter of a polytope $P$ is the maximum value of a shortest path between two vertices of $P$, where the path uses the edges of $P$ only. In contrast to the combinatorial diameter, the circuit diameter of $P$ is defined as the maximum value of a shortest path between two vertices of $P$, where the path uses potential edge directions of $P$ i.e., all edge directions that can arise by translating some of the facets of $P$. In this paper, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope, the Traveling Salesman polytope and the Fractional Stable Set polytope.

Recommendations

• The monotonic diameter of the perfect matching and shortest path polytopes
• On the circuit diameter of dual transportation polyhedra
• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• Upper bounds for the diameter and height of graphs of convex polyhedra
• On circuit diameter bounds via circuit imbalances

Cites work

• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• A counterexample to the Hirsch conjecture
• A linear bound on the diameter of the transportation polytope
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edges versus circuits: a hierarchy of diameters in polyhedra
• How tight is the corner relaxation? Insights gained from the stable set problem
• Improving bounds on the diameter of a polyhedron in high dimensions
• Maximum matching and a polyhedron with 0,1-vertices
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On certain polytopes associated with graphs
• On the Assignment Polytope
• On the circuit diameter conjecture
• On the circuit diameter of dual transportation polyhedra
• On the positive sums property and the computation of Graver test sets
• On the symmetric travelling salesman problem I: Inequalities
• Quadratic diameter bounds for dual network flow polyhedra
• Stable sets, corner polyhedra and the Chvàtal closure
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The hierarchy of circuit diameters and transportation polytopes
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The Hirsch conjecture for the fractional stable set polytope
• The traveling salesman problem in graphs with some excluded minors
• The travelling salesman problem and a class of polyhedra of diameter two

Cited in

(27)

• Edges versus circuits: a hierarchy of diameters in polyhedra
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• On the circuit diameter conjecture
• A polyhedral model for enumeration and optimization over the set of circuits
• On circuit diameter bounds via circuit imbalances
• An implementation of steepest-descent augmentation for linear programs
• Circuit walks in integral polyhedra
• Quadratic diameter bounds for dual network flow polyhedra
• The circuit diameter of the Klee-Walkup polyhedron
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• The Monotonic Diameter of the Perfect 2-matching Polytope
• The Hirsch conjecture for the fractional stable set polytope
• Constructing Clustering Transformations
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Inapproximability of shortest paths on perfect matching polytopes
• Circuit Imbalance Measures and Linear Programming
• On the Combinatorial Diameters of Parallel and Series Connections
• Circuits in extended formulations
• On circuit diameter bounds via circuit imbalances
• On combinatorial network flows algorithms and circuit augmentation for pseudoflows
• On the hardness of short and sign-compatible circuit walks
• Inapproximability of shortest paths on perfect matching polytopes
• Combinatorics of generalized parking-function polytopes
• On the circuit diameter conjecture for counterexamples to the Hirsch conjecture
• On circuit diameter and straight line complexity

This page was built for publication: On the circuit diameter of some combinatorial polytopes

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