Lab 04: Approximation Algorithms for TSP

The Travelling Salesman Problem (TSP) is a cornerstone of combinatorial optimization and computational complexity. In its classical form, TSP seeks the shortest possible route that visits each city exactly once and returns to the origin. This problem is NP-hard, and exact solutions become infeasible for large input sizes.

This lab focuses on approximation algorithms for:

• Metric TSP: Triangle inequality holds.
• Symmetric TSP: Cost between nodes is the same in both directions.
• Variants like MST-approximation and Christofides’ algorithm.

Introduction

The TSP has many practical applications in logistics, robotics, and circuit design. Since exact algorithms like brute force or dynamic programming (Held-Karp) are only suitable for small instances, we explore efficient approximations.

Key approximations covered:

1. MST-based 2-approximation for metric TSP.
2. Christofides’ Algorithm: A 1.5-approximation for symmetric metric TSP.
3. Greedy TSP Heuristic: Simple, fast, and surprisingly effective in many cases.

• Google Dork: [site:edu “TSP approximation MST Christofides”]

Approximate Algorithms for TSP

1. MST-based 2-Approximation Algorithm

Idea:

• Build a Minimum Spanning Tree (MST).
• Perform a preorder traversal to generate a tour.
• Return to the starting node.

import networkx as nx
 
def mst_approx_tsp(graph, start=0):
    mst = nx.minimum_spanning_tree(graph)
    tour = list(nx.dfs_preorder_nodes(mst, source=start))
    tour.append(start)
    return tour

2. Christofides’ Algorithm (1.5-Approximation)

Idea:

• Construct MST.
• Find odd-degree vertices in MST.
• Compute minimum-weight perfect matching on those.
• Combine MST + Matching = Eulerian multigraph.
• Form a Hamiltonian cycle by shortcutting repeated nodes.

Note: Requires a complete, symmetric graph satisfying triangle inequality.

from networkx.algorithms import matching
 
def christofides_tsp(graph):
    mst = nx.minimum_spanning_tree(graph)
 
    # Step 1: Find odd degree vertices
    odd_deg_nodes = [v for v in mst.nodes if mst.degree(v) % 2 == 1]
 
    # Step 2: Induce subgraph & find minimum weight perfect matching
    subgraph = graph.subgraph(odd_deg_nodes)
    match = matching.min_weight_matching(subgraph, maxcardinality=True, weight='weight')
 
    # Step 3: Combine MST and Matching
    multigraph = nx.MultiGraph()
    multigraph.add_edges_from(mst.edges(data=True))
    multigraph.add_edges_from(((u, v, {'weight': graph[u][v]['weight']}) for u, v in match))
 
    # Step 4: Euler tour and shortcut to Hamiltonian
    euler = list(nx.eulerian_circuit(multigraph))
    visited = set()
    path = []
    for u, _ in euler:
        if u not in visited:
            path.append(u)
            visited.add(u)
    path.append(path[0])
    return path

3. Greedy TSP Heuristic

Idea:

• Start at any node.
• Repeatedly visit the nearest unvisited node.

def greedy_tsp(graph, start=0):
    unvisited = set(graph.nodes)
    path = [start]
    unvisited.remove(start)
 
    current = start
    while unvisited:
        next_node = min(unvisited, key=lambda x: graph[current][x]['weight'])
        path.append(next_node)
        unvisited.remove(next_node)
        current = next_node
 
    path.append(start)
    return path

Example Usage

import matplotlib.pyplot as plt
import random
 
# Generate complete graph with random weights
G = nx.complete_graph(6)
for u, v in G.edges():
    G[u][v]['weight'] = random.randint(1, 20)
 
mst_tour = mst_approx_tsp(G)
christofides_tour = christofides_tsp(G)
greedy_tour = greedy_tsp(G)
 
print("MST Tour:", mst_tour)
print("Christofides Tour:", christofides_tour)
print("Greedy Tour:", greedy_tour)

Visualization

def plot_tour(graph, tour, title):
    pos = nx.spring_layout(graph)
    nx.draw(graph, pos, with_labels=True, node_color='lightblue')
    edges = [(tour[i], tour[i+1]) for i in range(len(tour)-1)]
    nx.draw_networkx_edges(graph, pos, edgelist=edges, edge_color='red', width=2)
    plt.title(title)
    plt.show()
 
# Plot different TSP tours
plot_tour(G, mst_tour, "MST-Based Approx TSP Tour")
plot_tour(G, christofides_tour, "Christofides TSP Tour")
plot_tour(G, greedy_tour, "Greedy TSP Tour")

Time and Space Complexity

Applications

1. Logistics & Delivery Routing
2. PCB Design & Chip Manufacturing
3. Autonomous Navigation
4. Tour Planning in Smart Cities
5. Genome Sequencing (as a Hamiltonian Path approximation)

Conclusion

Approximation algorithms like MST and Christofides offer near-optimal solutions to the TSP with significantly lower computational cost. While they do not guarantee the optimal tour, they provide bounded solutions that are practical for large-scale and real-time applications.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
   Introduction to Algorithms, 3rd/4th Edition, MIT Press.

2. Approximation Algorithms Lecture – MIT OpenCourseWare 

3. YouTube: Approximation for TSP