Publications (7)
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Eleon Bach, Alexander E. Black, Sophie Huiberts +1
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice,…
On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning 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 between points in its affine spac…
Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization
Jesús A. De Loera, Sean Kafer, Laura SanitÃ
Circuit-augmentation algorithms are generalizations of the Simplex method, where in each step one is allowed to move along a fixed set of directions, called circuits, that is a sup…
Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer +5
We study the {\sc Clique} problem in classes of intersection graphs of convex sets in the plane. The problem is known to be NP-complete in convex-set intersection graphs and straig…
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…
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…