coherent monotone paths 1exponential lower bounds 1Hirsch conjecture 1linear programming 1polytopes 1shadow simplex method 1
From the 1 of 6 linked papers with an AI index.
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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,…
cs.DS2026
Finding Short Paths on Simple Polytopes
Alexander E. Black, Raphael Steiner
We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and S…
cs.DS2025
Short circuit walks in fixed dimension
Alexander E. Black, Christian Nöbel, Raphael Steiner
Circuit augmentation schemes are a family of combinatorial algorithms for linear programming that generalize the simplex method. To solve the linear program, they construct a so-ca…