On circuit diameter bounds via circuit imbalances

DOI10.1007/S10107-024-02107-XMaRDI QIDQ6589764zbMATH OpenFDO

Authors Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh

Publication date 20 August 2024

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

combinatorial diameter, circuit imbalance measure of the constraint matrix

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Integer programming (90C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Recommendations

On circuit diameter bounds via circuit imbalances
Circuit Imbalance Measures and Linear Programming
On the circuit diameter of some combinatorial polytopes
On the circuit diameter conjecture
On the circuit diameter of dual transportation polyhedra

Cites work

scientific article; zbMATH DE number 1305542 (Why is no real title available?)
scientific article; zbMATH DE number 3365043 (Why is no real title available?)
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
A counterexample to the Hirsch conjecture
A polynomial cycle canceling algorithm for submodular flows
A primal-dual interior point method whose running time depends only on the constraint matrix
A quasi-polynomial bound for the diameter\\of graphs of polyhedra
A strongly polynomial minimum cost circulation algorithm
An implementation of steepest-descent augmentation for linear programs
Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
Circuit Imbalance Measures and Linear Programming
Circuits in extended formulations
Edges versus circuits: a hierarchy of diameters in polyhedra
Finding minimum-cost circulations by canceling negative cycles
Finding short paths on polytopes by the shadow vertex algorithm
Geometric random edge
Improving bounds on the diameter of a polyhedron in high dimensions
Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances
Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
On the circuit diameter conjecture
On the circuit diameter of dual transportation polyhedra
On the circuit diameter of some combinatorial polytopes
On the shadow simplex method for curved polyhedra
Pivot rules for circuit-augmentation algorithms in linear optimization
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
Sensitivity theorems in integer linear programming
Subspaces with well-scaled frames
The hierarchy of circuit diameters and transportation polytopes
The minimum mean cycle-canceling algorithm for linear programs
Variation of cost functions in integer programming

Cited in

(1)

Circuit Imbalance Measures and Linear Programming

This page was built for publication: On circuit diameter bounds via circuit imbalances

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