Novel Approximation Techniques for Traveling Salesman Problems
Final Report Abstract
The research project contributed to the knowledge of techniques in the field of Combinatorial Optimization for the design of approximation algorithms. Following the goal to approach approximating the metric traveling salesman problem, we increased the understanding of the precise obstacles and the development of techniques to handle them. The proposal had a number of ambitious goals. Some of the direct goals were fully attained and a number of related high-profile results were obtained. In the following we limit our attention to the three most important results of the project. As a particularly important goal that was achieved, we obtained the best-possible quality guarantees that we can expect in polynomial time for the well studied problem Unsplittable Flow on a Path. This work marks the end of a study that produced a large number of high-profile publications over a long period of time; the PI’s involvement in this line of research started 2015 and while steps forward were to be expected, a final resolution of the problem was not at the horizon at the start of the project. A further direct goal of the project was an improved approximation ratio for a generalization of the Traveling Salesman Problem called ordered TSP. The approximation algorithm obtained within the project does not only provide the aimed-for result, but it also introduces new techniques that already have proved useful for further results that the PI and his co-authors obtained after the end of the funding period. For Euclidean TSP, in the end of the project the PI and his co-author obtained an important step forward. The Euclidean Plane is one of the most natural spaces that one can think of: The cities are points determined by two coordinates (say an x-axis and a y-axis) and the distance between points is the length of a line segment connecting them. Within this space, a (1 + ) approximation is the best we can hope for in polynomial time. Our contribution is such an algorithm that has the best possible running time (up to constant factors) that we can hope for: it both has linear running time in the number of points and the best running time with respect to the error that is achievable unless well-established conjectures fail. Furthermore, the algorithm itself is relatively simple – the complication is in the analysis of the algorithm. Given the simplicity of the algorithm, it is not hard to implement it. It therefore has potential practical uses. While this result is among the most important results of the project, as of now the article is still under review.
Publications
-
A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 894-905. Society for Industrial and Applied Mathematics.
Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Pittu, Madhusudhan Reddy & Wiese, Andreas
-
A 3/2-Approximation for the Metric Many-Visits Path TSP. SIAM Journal on Discrete Mathematics, 36(4), 2995-3030.
Bérczi, Kristóf; Mnich, Matthias & Vincze, Roland
-
A PTAS for unsplittable flow on a path. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 289-302. ACM.
Grandoni, Fabrizio; Mömke, Tobias & Wiese, Andreas
-
Approximating Maximum Edge 2-Coloring by Normalizing Graphs. Lecture Notes in Computer Science, 29-44. Springer Nature Switzerland.
Mömke, Tobias; Popa, Alexandru; Roshany-Tabrizi, Aida; Ruderer, Michael & Vincze, Roland
-
Capacitated Vehicle Routing in Graphic Metrics. Symposium on Simplicity in Algorithms (SOSA), 114-123. Society for Industrial and Applied Mathematics.
Mömke, Tobias & Zhou, Hang
-
Approximating Traveling Salesman Problems Using a Bridge Lemma. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1166-1177. Society for Industrial and Applied Mathematics.
Böhm, Martin; Friggstad, Zachary; Mömke, Tobias & Spoerhase, Joachim
