6 citations · 19 across the 16 of their papers we have counts for
23 papers
Better approximation guarantee for Asymmetric TSP
Jens Vygen
We improve the approximation ratio for the Asymmetric TSP to less than 15. We also obtain improved ratios for the special case of unweighted digraphs and the generalization where w…
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 $…
Packing cycles in planar and bounded-genus graphs
Niklas Schlomberg, Hanjo Thiele, Jens Vygen
We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. Here di…
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.…
Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
Markus Ahrens, Dorothee Henke, Stefan Rabenstein +1
We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra's algorithm to find shortest paths in huge incomplete grid…