25 citations · 57 across the 24 of their papers we have counts for
4 papers · 1 filter
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…
Incremental-Decremental Maximization
Yann Disser, Max Klimm, Annette Lutz +1
We introduce a framework for incremental-decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is trans…
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+ε}+\…
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…