1 citations · 1 across the 5 of their papers we have counts for
5 papers
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…
Circuits in Extended Formulations
Steffen Borgwardt, Matthias Brugger
Circuits and extended formulations are classical concepts in linear programming theory. The circuits of a polyhedron are the elementary difference vectors between feasible points a…
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…
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…
Additive colourful Carathéodory type results with an application to radii
Matthias Brugger, Maximilian Fiedler, Bernardo González Merino +1
In this paper we study the behavior of the circumradius with respect to the Minkowski addition in generalized Minkowski spaces. To do so, we solve additive colourful Carathéodory t…