6 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, JarosÅaw Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
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 convex quadratic maximization
Eleon Bach, Yann Disser, Sophie Huiberts +1
We prove that the active-set method needs an exponential number of iterations in the worst-case to maximize a convex quadratic function subject to linear constraints, regardless of…
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…
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 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…