10 grudnia 2019 10:15
[Seminarium ZOK] Tobias Moemke o "Beating the 2.5-Barrier for TSP with Linear Precedence Constraints" (unpublished)
Tytuł: Beating the 2.5-Barrier for TSP with Linear Precedence Constraints (unpublished)
Prelegent: Tobias Moemke
Czas i miejsce: wtorek, 10-go grudnia 2019, 10:15, sala 310.
Streszczenie:
Precedence constrained TSP (PCTSP) is a well studied problem in combinatorial optimization. Given a complete graph with metric edge costs and a set of vertex pairs (s_i,t_i), the goal is to find a minimum cost Hamiltonian tour visiting s_i before t_i for each i. In 1997, Charikar et al. showed that, for general precedence constrains, finding a constant approximation is NP-hard.
We consider the setting of precedence constraints that determine a linearly ordered subset of vertices. The problem is called ordered TSP (OTSP) in the literature. A direct application of the famous Christofides-Serdyukov algorithm to OTSP gives a 2.5-approximation and only sub-constant improvements of this bound were previously known. We obtain the first constant improvement by presenting an approximation algorithm for OTSP with performance guarantee 2.5 - epsilon for a fixed constant epsilon.
Our algorithm is based on rounding a novel LP relaxation for OTSP based on multi-commodity flows. A key step in the rounding is to solve an auxiliary problem, which abstracts the difficulties originating from the precedence constraints. We call this problem multi-commodity spanning forest problem (MCSF) and its goal is to find a minimum spanning forest such that each tree contains exactly one pair from a given set of vertex pairs. Our analysis crucially relies on ideas from the iterated rounding framework developed by Byrka et al. (2010), even though we solve our LP only once. To the best of our knowledge, our result is the first application of this framework to a routing problem.