Ankündigung Vortrag

Im Rahmen des Kolloquiums des Instituts für Informatik hält

Frau Prof. Anke van Zuylen (College of William & Mary)

am Dienstag, den 25.06.13 um 17:00  Uhr,
in Seminarraum 307 (Robert-Mayer-Str 11-15, 3.OG)

einen Vortrag zum Thema

The traveling salesman problem, cycle covers and the subtour LP


The traveling salesman problem (TSP) is perhaps the most famous problem in combinatorial optimization: given a set of cities and the distances for traveling between each pair of cities, the goal of the problem is to find the shortest tour that visits each city at least once and returns to its starting point. We consider the case when the distances are symmetric.

The symmetric traveling salesman problem is NP-hard and has a 3/2-approximation algorithm due to Christofides (1976). A question that has been open for several decades is whether it is possible to find better approximation algorithms. A natural direction for making progress on this question is the study of the integrality gap of a linear programming (LP) relaxation called the subtour LP. The subtour LP is known to give excellent lower bounds on TSP instances in practice, generally coming within a percent or two of the length of the optimal tour. However, its theoretical worst-case is not well understood. It has been known for 30 years that the subtour LP bound is at least 2/3 times the length of an optimal tour for all instances of the problem, and it is known that there are instances such that it is at most 3/4 times the length of an optimal tour, but no progress has been made in 30 years in tightening these bounds.

In this talk, we review some of the results that are known about the subtour LP, and we give some new results that refine our understanding of the relation between the subtour LP bound and minimum cost cycle covers; a cycle cover of a graph is a set of node-disjoint cycles such that every node is contained in exactly one cycle. We resolve a conjecture of Boyd and Carr characterizing the worst case ratio of an optimal cycle cover to the subtour LP bound. We further extend these results to triangle-free cycle covers under an assumption on the structure of the optimal subtour LP solution.

This is based on joint work with Philipp Klodt, Jiawei Qian, Frans Schalekamp, and David Williamson.

Es lädt ein: Dr. M. Poloczek

Zusätzliche Informationen