Novel Approximation Techniques for Traveling Salesperson Problems

• Applicant: Professor Dr. Tobias Mömke
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 277883503

This research project aims to advance current developments on approximation algorithms for the metric Traveling Salesperson Problem (metric TSP) and related variants.The classical TSP is modeled as a graph problem where we are given a set of cities (vertices) and a set of roads (edges) connecting them, with a cost (e.g., distance, time) associated to each edge. The objective is to the find the tour of minimum cost that visits each vertex exactly once and returns to the starting point.The metric TSP is a variant of TSP that adds the property that the edge costs have to be non-negative, symmetric, and satisfy the triangle inequality. The best polynomial time algorithm for the metric TSP is the 1.5-approximation algorithm, obtained by Christofides in 1976. Finding an improvement on this result remains an important problem, and extensive research suggests that this may only be achieved with better algorithmic techniques. Some recent techniques applied on the related graph-TSP, as well as for the path version of metric TSP give new hope to finally overcome the difficulties.We plan to develop novel approximation techniques for the metric TSP and its variants, such as the graph-TSP. We aim to approach this goal gradually, by employing some of the recent techniques towards improving algorithms for some other TSP variants and related problems, with candidates such as k-TSP, the minimum latency problem, and the 2-edge-connected spanning subgraph problem. Some of these techniques are sum of squares, semidefinite programming, iterative linear programming, thin spanning trees, and removable pairings. The PI played a central role in the development and application of the last technique mentioned, removable pairings, which improved on the then best graph-TSP result and is utilized in the currently best graph-TSP algorithm.Finding improved approximation algorithms for the main problems addressed in this project would have considerable impact in the field and will have the potential to facilitate the solution of practical real world problem instances, specifically in areas such as logistics, genetics, manufacturing, telecommunications and neuroscience where TSP has seen wide applications.Independent of whether we are able to solve these difficult problems, the new and novel techniques and algorithms that we expect to obtain in the project will be meaningful in their own right and are likely to advance the development of approximation algorithms even beyond the scope of the project.

• DFG Programme: Research Grants