11th Colloquium of the Research Area C3C3 Kolloquium / Colloquium of the Research Area C3

by Bill Cook (University of Waterloo), Luise Puhlmann (Forschungsinstitut für Diskrete Mathematik)

Friday Jul 18, 2025, 9:30 AM → 12:00 PM Europe/Berlin

Friedrich-Hirzebruch-Allee 8/0-016 - Room 0.016 (Computer Science Building)

Venue:  Computer Science Building (Friedrich-Hirzebruch-Allee 8), room 0.016

09:30    Coffee and Tea (room 2.075)

10:00    Bill Cook: TSP cut  separation

10:45    Coffee break (room 2.075)

11:15    Luise Puhlmann: Improved guarantees for the (asymmetric) a priori TSP

 

Bill Cook: TSP cut separation

Cutting-plane methods have been used to solve large-scale instances of the traveling salesman problem. The key step requires algorithms for finding linear inequalities valid for all tours, but violated by the solution to the current linear-programming relaxation. This is known as the cut-separation problem. We discuss recent work in TSP cut separation that permitted earlier this year the computation of an optimal 81,998-stop tour using point-to-point walking distances obtained with the Open Source Routing Machine (OSRM). The focus of the talk will be on research questions that could drive further improvements in cutting-plane methods for the TSP and related discrete optimization models.

 

Luise Puhlmann: Improved guarantees for the (asymmetric) a priori TSP

In the a priori TSP, we are given a metric space (V, c) and an activation probability p(v) for each customer v \in V. We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a so called "master route solution", consisting of a TSP tour for S and two edges connecting every customer v \in V \ S to a nearest customer in S. We analyze how to find the best choice for S when using random sampling techniques and provide almost matching lower and upper bounds as well as improved approximation guarantees.

The asymmetric version (i.e. not requiring c(v,w) = c(w,v)) seems to be much harder. We show how to obtain an O(\sqrt(n))-approximation algorithm, and also achieve a quasi-polynomial time algorithm with a poly-logarithmic approximation guarantee. Thus, we beat the adaptivity gap (that measures how bad the best a priori tour can be in comparison to the expected length of the a posteriori optimum tour).

This is joint work with Jannis Blauth, Meike Neuwohner, and Jens Vygen (for the symmetric version) and with Manuel Christalla and Vera Traub (for the asymmetric version).