4 papers
Reducing Path TSP to TSP
Vera Traub, Jens Vygen, Rico Zenklusen
We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an -a…
Vehicle Routing with Subtours
Stephan Held, Jochen Könemann, Jens Vygen
When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items a…
Few Sequence Pairs Suffice: Representing All Rectangle Placements
Jannik Silvanus, Jens Vygen
We consider representations of general non-overlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representat…
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich +3
In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph , edge costs , terminal pairs , and…