Explanipedia

A better-than-1.6-approximation for prize-collecting TSP Open

Jannis Blauth, Nathan Klein, Martin Nägele · 2025

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 solution is then measured by adding the length of the tour and the…

Cost allocation for set covering: The happy nucleolus Open

Jannis Blauth, Antonia Ellerbrock, Vera Traub, Jens Vygen · 2024

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, and so that the excess vector is lexicographically maximized. This hap…

Vehicle routing with time-dependent travel times: Theory, practice, and benchmarks Open

Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub , et al. · 2024

We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arriva…

Cost Allocation for Set Covering: the Happy Nucleolus Open

Jannis Blauth, Antonia Ellerbrock, Vera Traub, Jens Vygen · 2024

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 of players pays more than covering this subset would cost), …

Improved guarantees for the a priori TSP Open

Jannis Blauth, Meike Neuwohner, Luise Puhlmann, Jens Vygen · 2023

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 $(V,c)$ and an activation probability $p(v)$ for each custom…

A Better-Than-1.6-Approximation for Prize-Collecting TSP Open

Jannis Blauth, Nathan Klein, Martin Nägele · 2023

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 solution is then measured by adding the length of the tour and the…

An improved approximation guarantee for Prize-Collecting TSP Open

Jannis Blauth, Martin Nägele · 2022

We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may not include a vertex of the input graph in th…

Improving the approximation ratio for capacitated vehicle routing Open

Jannis Blauth, Vera Traub, Jens Vygen · 2022

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 the unit-demand case and the splittable variant. Our results …

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks Open

Jannis Blauth, Stephan Held, Dirk Müller, Niklas Schlomberg, Vera Traub , et al. · 2022

We develop theoretical foundations and practical algorithms for vehicle routing with time-dependent travel times. We also provide new benchmark instances and experimental results. First, we study basic operations on piecewise linear arriva…

Improving the Approximation Ratio for Capacitated Vehicle Routing Open

Jannis Blauth, Vera Traub, Jens Vygen · 2020

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 the unit-demand case and the splittable variant. Our results …

Jannis Blauth YOU? Author Swipe