4 papers
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…
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…
Optimal tables for asymmetric numeral systems
Raphael S. Steiner, Mirko De Vita, Endri Bezati
We present several algorithms to generate tables for asymmetric numeral systems and prove that they are optimal in terms of discrepancy. In turn, this gives rise to the strongest p…
Complexity of polytope diameters via perfect matchings
Christian Nöbel, Raphael Steiner
The Circuit diameter of polytopes was introduced by Borgwardt, Finhold and Hemmecke as a fundamental tool for the study of circuit augmentation schemes for linear programming and f…