1 citations · 2 across the 7 of their papers we have counts for
4 papers · 1 filter
On Circuit Imbalance and 0/1 Circuits for Coloring and Forest Problems
Steffen Borgwardt, Nicholas Crawford, Sean Kafer +2
Circuits are fundamental objects in linear programming and oriented matroid theory, representing the elementary difference vectors of a polyhedron. A recent concept introduced by D…
On the Hardness of Short and Sign-Compatible Circuit Walks
Steffen Borgwardt, Weston Grewe, Sean Kafer +2
The circuits of a polyhedron are a superset of its edge directions. Circuit walks, a sequence of steps along circuits, generalize edge walks and are "short" if they have few steps…
On the Simplex method for 0/1 polytopes
Alexander Black, Jesús De Loera, Sean Kafer +1
We present new pivot rules for the Simplex method for LPs over 0/1 polytopes. We show that the number of non-degenerate steps taken using these rules is strongly polynomial and eve…
On the Circuit Diameter of some Combinatorial Polytopes
Sean Kafer, Kanstantsin Pashkovich, Laura Sanità
The combinatorial diameter of a polytope is the maximum value of a shortest path between two vertices of , where the path uses the edges of only. In contrast to the comb…