3 citations · 3 across the 3 of their papers we have counts for
5 papers
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…
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…
A unified worst case for classical simplex and policy iteration pivot rules
Yann Disser, Nils Mosis
We construct a family of Markov decision processes for which the policy iteration algorithm needs an exponential number of improving switches with Dantzig's rule, with Bland's rule…
An Improved Algorithm for Open Online Dial-a-Ride
Julia Baligacs, Yann Disser, Nils Mosis +1
We consider the open online dial-a-ride problem, where transportation requests appear online in a metric space and need to be served by a single server. The objective is to minimiz…