3 papers
math.CO2023
On the Circuit Diameter Conjecture for Counterexamples to the Hirsch Conjecture
Alexander E. Black, Steffen Borgwardt, Matthias Brugger
Circuit diameters of polyhedra are a fundamental tool for studying the complexity of circuit augmentation schemes for linear programming and for finding lower bounds on combinatori…
cs.DM2021
On the Complexity of Recognizing Integrality and Total Dual Integrality of the -Closure
Matthias Brugger, Andreas S. Schulz
The -closure of a rational polyhedron is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system $Ax \le…
math.CO2019
Limitations of the Hyperplane Separation Technique for Bounding the Extension Complexity of Polytopes
Matthias Brugger
We illustrate the limitations of the hyperplane separation bound, a non-combinatorial lower bound on the extension complexity of a polytope. Most notably, this bounding technique i…