Edges versus circuits: a hierarchy of diameters in polyhedra
From MaRDI portal
(Redirected from Publication:1707378)
Combinatorial aspects of matroids and geometric lattices (05B35) 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) Oriented matroids in discrete geometry (52C40) Combinatorial complexity of geometric structures (52C45) Linear programming (90C05) Extreme-point and pivoting methods (90C49)
Abstract: The study of the graph diameter of polytopes is a classical open problem in polyhedral geometry and the theory of linear optimization. In this paper we continue the investigation initiated in [4] by introducing a vast hierarchy of generalizations to the notion of graph diameter. This hierarchy provides some interesting lower bounds for the usual graph diameter. After explaining the structure of the hierarchy and discussing these bounds, we focus on clearly explaining the differences and similarities among the many diameter notions of our hierarchy. Finally, we fully characterize the hierarchy in dimension two. It collapses into fewer categories, for which we exhibit the ranges of values that can be realized as diameters.
Recommendations
Cites work
- A polynomial oracle-time algorithm for convex integer minimization
- An update on the Hirsch conjecture
- Criss-cross methods: A fresh view on pivot algorithms
- scientific article; zbMATH DE number 3365043 (Why is no real title available?)
- Linear programming duality: an introduction to oriented matroids
- New Finite Pivoting Rules for the Simplex Method
- On the circuit diameter of dual transportation polyhedra
- Oriented Matroids
- The hierarchy of circuit diameters and transportation polytopes
Cited in
(23)- On the diameter of the edge cover polytope
- The hierarchy of circuit diameters and transportation polytopes
- 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
- The diameter of the ridge-graph of a cyclic polytope
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- On the circuit diameter of some combinatorial polytopes
- Constructing Clustering Transformations
- scientific article; zbMATH DE number 5030014 (Why is no real title available?)
- Pivot rules for circuit-augmentation algorithms in linear optimization
- On circuit diameter bounds via circuit imbalances
- Circuit and Graver walks and linear and integer programming
- On combinatorial network flows algorithms and circuit augmentation for pseudoflows
- On the hardness of short and sign-compatible circuit walks
- Primitive zonotopes
- Combinatorics of generalized parking-function polytopes
- On the circuit diameter conjecture for counterexamples to the Hirsch conjecture
- Edge-directions of standard polyhedra with applications to network flows
This page was built for publication: Edges versus circuits: a hierarchy of diameters in polyhedra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1707378)
