Circuit walks in integral polyhedra

DOI10.1016/J.DISOPT.2019.100566MaRDI QIDQ2673232zbMATH OpenOpenAlexWikidataFDO

Authors Steffen Borgwardt, Charles Viss

Publication date 9 June 2022

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear programminginteger programmingdiametertotal unimodularitycircuit walksedge walks

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• A polyhedral model for enumeration and optimization over the set of circuits
• On the circuit diameter conjecture
• On the circuit diameter of some combinatorial polytopes
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Edge-directions of standard polyhedra with applications to network flows

Cites work

• scientific article; zbMATH DE number 3294139 (Why is no real title available?)
• scientific article; zbMATH DE number 3365043 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A counterexample to the Hirsch conjecture
• A polynomial oracle-time algorithm for convex integer minimization
• Adjacency on polymatroids
• Criss-cross methods: A fresh view on pivot algorithms
• Decomposition theorems for linear programs
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Good clusterings have large volume
• New Finite Pivoting Rules for the Simplex Method
• Nonlinear discrete optimization. An algorithmic theory
• 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 diameter of partition polytopes and vertex-disjoint cycle cover
• On the foundations of linear and integer linear programming I
• Oriented Matroids
• Quadratic diameter bounds for dual network flow polyhedra
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• The Hirsch conjecture is true for (0,1)-polytopes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The circuit diameter of the Klee-Walkup polyhedron
• The hierarchy of circuit diameters and transportation polytopes

Cited in

(7)

• Circuits in extended formulations
• Constructing Clustering Transformations
• Sublinear circuits for polyhedral sets
• Circuit Imbalance Measures and Linear Programming
• An implementation of steepest-descent augmentation for linear programs
• Circuit Walks in Integral Polyhedra
• A polyhedral model for enumeration and optimization over the set of circuits

This page was built for publication: Circuit walks in integral polyhedra

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