3 citations · 6 across the 7 of their papers we have counts for
8 papers
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…
Cost Allocation for Set Covering: the Happy Nucleolus
Jannis Blauth, Antonia Ellerbrock, Vera Traub +1
We consider cost allocation for set covering problems. We allocate as much cost to the elements (players) as possible without violating the group rationality condition (no subset o…
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…