Course full name
Advanced Techniques for Combinatorial Algorithms
Course ID number
1920-87R-04
1-2 TSP
Completion requirements
Opened: Thursday, 28 May 2020, 12:00 AM
Let G be a complete undirected graph whose edge weights are all 1 or 2 (it is a special kind of metric).
Give a 4/3-approximation algorithm for Min Traveling Salesperson Problem (Min TSP) for this special case.
Hint. First find a 2-matching in G. A 2-matching is a subset M of the edges such that each vertex has exactly 2 edges incident on it. There is a polytime algorithm for this step (see https://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles/8570#8570)