3 citations · 3 across the 3 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
math.OC2025
Lower bounds for ranking-based pivot rules
Yann Disser, Georg Loho, Matthew Maat +1
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games ea…
cs.DM2025
An Unconditional Lower Bound for the Active-Set Method in Almost-Linear Programming
Eleon Bach, Yann Disser, Sophie Huiberts +1
We prove that, for every fixed , the active-set method requires exponentially many iterations in the worst case to maximize a convex objective of the form $(x_1)^{1+ε}+\…
cs.DM2025
An unconditional lower bound for the active-set method on the hypercube
Yann Disser, Nils Mosis
The existence of a polynomial-time pivot rule for the simplex method is a fundamental open question in optimization. While many super-polynomial lower bounds exist for individual o…