3 papers
cs.DS2025
Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
Jannis Blauth, Christian Nöbel, Rico Zenklusen
One of the most elementary spreading models on graphs can be described by a fire spreading from a burning vertex in discrete time steps. At each step, all neighbors of burning vert…
cs.DS2025
A Constant-Factor Approximation for Directed Latency
Jannis Blauth, Ramin Mousavi
In the Directed Latency problem, we are given an asymmetric metric space on a set of clients and a depot . We are looking for a path starting in t…
cs.DS2020
Improving the Approximation Ratio for Capacitated Vehicle Routing
Jannis Blauth, Vera Traub, Jens Vygen
We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for th…