3 citations · 6 across the 7 of their papers we have counts for
7 papers · 1 filter
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…
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…
Improved guarantees for the a priori TSP
Jannis Blauth, Meike Neuwohner, Luise Puhlmann +1
We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $…
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…
An improved approximation guarantee for Prize-Collecting TSP
Jannis Blauth, Martin Nägele
We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (…
Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
Jannis Blauth, Stephan Held, Dirk Müller +4
We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results.…
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…