On the Circuit Diameter of Some Combinatorial Polytopes

DOI10.1137/17M1152115zbMath1416.52006arXiv1709.09642MaRDI QIDQ4644426

Kanstantsin Pashkovich, Sean Kafer, 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

polytopescircuit diametercombinatorial diametermatching polytopetraveling salesman polytopefractional stable set 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)

Related Items

On circuit diameter bounds via circuit imbalances, An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, Inapproximability of shortest paths on perfect matching polytopes, Constructing Clustering Transformations, A polyhedral model for enumeration and optimization over the set of circuits, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Cites Work

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