Neuartige Approximationstechniken für Traveling Salesperson Probleme
Zusammenfassung der Projektergebnisse
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. At the start of the project, the main focus was the study of relevant versions of the traveling salesman problem (TSP) with cost functions that provide some additional structure. These measures included doubling spaces which provide a natural dimensionality measure for metric spaces. Doubling spaces generalize the practically relevant Euclidean space which in 3-dimensions models the space we live in. The gained insights lead to several publications. We were able to obtain a polynomial time algorithm which guarantees an almost exact outcome for a version of TSP called Maximum Scatter TSP (MSTSP) in the spaces mentioned above. The problem MSTSP models industrial situations in which tool operations are performed to a work piece. Since the operation (like, e.g., drilling) heats up the work piece, operations located directly beside each other should not be consecutive in the sequence in order to let the work piece cool down. The existence of fast algorithms that guarantee an exact solution or substantially faster approximation algorithms would refute long standing complexity conjectures such as the famous P vs NP question. Furthermore, studying the structure of TSP instances led to algorithms for a problem that models the decision process of where to build airports in order to provide connectivity of the clients with railways. One key aim of technique development within the project was to extend the understanding of properties provided by solutions to linear programming relaxations. In recent years, there was a fast and deep development of Sum of Squares techniques. Roughly speaking, one can describe these techniques as starting from modeling an algorithmic problem as a mathematical program which we cannot solve. We relax the program to a simpler one that is solvable in polynomial time and automatically strengthen it again. The aim is to increase the quality of the solution without losing the possibility to compute a solution. In the project we showed that for a classical scheduling problem, some of the strong strengthening methods have provably limited capacities. The technical insights discovered in the early stages of the project turned out to be useful for resource allocation and scheduling problems. In particular, the research improved the knowledge of a problem called unsplittable flow on a path (UFP), which has applications in various areas including the allocation of ratio frequencies over time, scheduling tasks on satellites, and assigning cars to customers in car sharing. The outcome of this research was to overcome some fundamental barriers on the way to a theoretically optimal approximation algorithm, polynomial time algorithms computing almost optimal solutions for several practically relevant situations, and the currently best approximation algorithm for the problem. Furthermore, the techniques developed for UFP had applications for a segmentation problem from Computational Biology called the Minimum Error Correction Problem (MEC). In an interdisciplinary work with the Bioinformatics research group of the Max Planck Institute for Informatics, we obtained approximation schemes for a relevant class of instances.
Projektbezogene Publikationen (Auswahl)
- “Maximum Scatter TSP in Doubling Metrics.” In: SODA. 2017, pp. 143–153
László Kozma and Tobias Mömke
(Siehe online unter https://doi.org/10.1137/1.9781611974782.10) - “To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.” In: SODA. 2017, pp. 2411–2422
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(Siehe online unter https://doi.org/10.1137/1.9781611974782.159) - “A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes.” In: STOC. 2018, pp. 607–619
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou
(Siehe online unter https://doi.org/10.1145/3188745.3188894) - “A QPTAS for Gapless MEC.” In: ESA. Vol. 112. LIPIcs. 2018, 34:1–34:14
Shilpa Garg and Tobias Mömke
(Siehe online unter https://doi.org/10.4230/LIPIcs.ESA.2018.34) - “Approximating Airports and Railways.” In: STACS. Vol. 96. LIPIcs. 2018, 5:1–5:13
Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke
(Siehe online unter https://doi.org/10.4230/LIPIcs.STACS.2018.5) - “Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines.” In: Math. Program. 172.1-2 (2018), pp. 231–248
Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, and Andreas Wiese
(Siehe online unter https://doi.org/10.1007/s10107-017-1152-5)
