Edges versus circuits: a hierarchy of diameters in polyhedra

DOI10.1515/advgeom-2016-0020zbMath1386.52008arXiv1409.7638OpenAlexW2964045245MaRDI QIDQ1707378

Steffen Borgwardt, Elisabeth Finhold, Jesús A. De Loera

Publication date: 29 March 2018

Published in: Advances in Geometry (Search for Journal in Brave)

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

zbMATH Keywords

matroidsdiameter of polyhedragraph of polyhedraone-skeleton of polytopes

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Computational aspects related to convexity (52B55) Linear programming (90C05) Combinatorial aspects of matroids and geometric lattices (05B35) Oriented matroids in discrete geometry (52C40) Extreme-point and pivoting methods (90C49) Combinatorial complexity of geometric structures (52C45)

Related Items

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ The circuit diameter of the Klee-Walkup polyhedron ⋮ On circuit diameter bounds via circuit imbalances ⋮ An implementation of steepest-descent augmentation for linear programs ⋮ Circuit walks in integral polyhedra ⋮ The hierarchy of circuit diameters and transportation polytopes ⋮ Constructing Clustering Transformations ⋮ On the Circuit Diameter of Some Combinatorial Polytopes ⋮ On the circuit diameter conjecture ⋮ Primitive zonotopes ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Cites Work

• Unnamed Item
• An update on the Hirsch conjecture
• A polynomial oracle-time algorithm for convex integer minimization
• Linear programming duality: an introduction to oriented matroids
• Criss-cross methods: A fresh view on pivot algorithms
• The hierarchy of circuit diameters and transportation polytopes
• On the Circuit Diameter of Dual Transportation Polyhedra
• New Finite Pivoting Rules for the Simplex Method
• Oriented Matroids