3. Metric TSP

Shortest cycle in graph that satisfies the triangle inequality that visits every graph at least once.

Same as: Hamiltonian cycle with lowest weight in fully connected graph, where every edge weight is the shortest path distance between two nodes.

Approximation

• Find MST in fully connected graph
• Double every edge
• Follow cycle and use shortcut if already visited

Weight MST $\le$ Weight lowest-weight Hamilton cycle (any Hamiltonian path in cycle is candidate for MST) $⟹$ Weight approximation $\le 2\cdot$ weight lowest-weight Hamilton cycle

Approximation using Matchings

• Find MST in fully connected graph
• Find minimal matchings of all nodes with uneven degree
• Follow cycle and use shortcut if already visited