3 papers
cs.DS2026
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.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 Better-Than-1.6-Approximation for Prize-Collecting TSP
Jannis Blauth, Nathan Klein, Martin Nägele
Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solutio…