A note on the approximability of deepest-descent circuit steps

DOI10.1016/j.orl.2021.02.003OpenAlexW3135613333MaRDI QIDQ2060534

Andreas Emil Feldmann, Martin Koutecký, Cornelius Brand, Steffen Borgwardt

Publication date: 13 December 2021

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingcircuitscomplexity theorydeepest-descent steps

Mathematics Subject Classification ID

Computer science (68-XX) Operations research, mathematical programming (90-XX)

Related Items

Inapproximability of shortest paths on perfect matching polytopes

Cites Work

• Edge-directions of standard polyhedra with applications to network flows
• Nonlinear discrete optimization. An algorithmic theory
• NP is as easy as detecting unique solutions
• On the positive sums property and the computation of Graver test sets
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• An implementation of steepest-descent augmentation for linear programs
• On the Circuit Diameter of Dual Transportation Polyhedra
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the foundations of linear and integer linear programming I
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item