25 citations · 57 across the 24 of their papers we have counts for
9 papers · 1 filter
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…
Unified greedy approximability beyond submodular maximization
Yann Disser, David Weckbecker
We consider classes of objective functions of cardinality constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new c…
Evacuating Two Robots from a Disk: A Second Cut
Yann Disser, Sören Schmitt
We present an improved algorithm for the problem of evacuating two robots from the unit disk via an unknown exit on the boundary. Robots start at the center of the disk, move at un…
General Bounds for Incremental Maximization
Aaron Bernstein, Yann Disser, Martin Groß
We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardi…
The Complexity of Computing a Robust Flow
Yann Disser, Jannik Matuschke
Robust network flows are a concept for dealing with uncertainty and unforeseen failures in the network infrastructure. They and their dual counterpart, network flow interdiction, h…
A general lower bound for collaborative tree exploration
Yann Disser, Frank Mousset, Andreas Noever +2
We consider collaborative graph exploration with a set of agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other ver…
The Simplex Algorithm is NP-mighty
Yann Disser, Martin Skutella
We propose to classify the power of algorithms by the complexity of the problems that they can be used to solve. Instead of restricting to the problem a particular algorithm was de…