25 citations · 57 across the 24 of their papers we have counts for
41 papers
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
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…
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 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…
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…
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
Yann Disser, Svenja M. Griesbach, Max Klimm +1
We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously ap…
A -Approximation for Tricolored Non-crossing Euclidean TSP
Júlia Baligács, Yann Disser, Andreas Emil Feldmann +1
In the Tricolored Euclidean Traveling Salesperson problem, we are given~ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (…
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…
Exploration of graphs with excluded minors
Julia Baligacs, Yann Disser, Irene Heinrich +1
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and…
Incremental Maximization via Continuization
Yann Disser, Max Klimm, Kevin Schewior +1
We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also d…
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…
Tight analysis of the lazy algorithm for open online dial-a-ride
Julia Baligacs, Yann Disser, Farehe Soheil +1
In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time.…
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Johannes Blum, Yann Disser, Andreas Emil Feldmann +2
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system with two families of subsets of .…
Fractionally Subadditive Maximization under an Incremental Knapsack Constraint
Yann Disser, Max Klimm, Annette Lutz +1
We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an o…
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…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Improved Lower Bound for Competitive Graph Exploration
Alexander Birx, Yann Disser, Alexander V. Hopp +1
We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting…
An Exponential Lower Bound for Zadeh's pivot rule
Yann Disser, Oliver Friedmann, Alexander V. Hopp
The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, determinist…
Improved Bounds for Open Online Dial-a-Ride on the Line
Alexander Birx, Yann Disser, Kevin Schewior
We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a…
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…
Travelling on Graphs with Small Highway Dimension
Yann Disser, Andreas Emil Feldmann, Max Klimm +1
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] a…
Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
Alexander Birx, Yann Disser
The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests appear over time and may be served in any order by a single server w…
Tight bounds for undirected graph exploration with pebbles and multiple agents
Yann Disser, Jan Hackfeld, Max Klimm
We study the problem of deterministically exploring an undirected and initially unknown graph with vertices either by a single agent equipped with a set of pebbles, or by a set…