Week 2: TSP - Branch and Bound, Approximation Methods

Question 1

Branch-and-bound Method

Answer 1

This is an improvement on exhaustive search, as it eliminates solutions that can’t be more optimal than the current most optimal solution.

The speed is rather slow. A complete tour must be calculated to verify how its compares to other branches.

Question 2

Approximate Algorithms

Answer 2

These algorithms compute decent solutions and are bounded by how close they are to the optimal solution.

The speed is fast, usually in polynomial time.

Question 3

Heuristics

Answer 3

This approach incorporates information about special cases and instances, but there’s no guarantee for optimality.

The speed is fast.

Question 4

Meta-heuristics

Answer 4

These are general heuristic techniques that can be applied to many different problems.

Examples: simulated annealing, genetic algorithms

Question 5

Hamiltonian Cycles

Answer 5

A NP-Complete problem where you pass through every vertex of a connected graph exactly once.

Question 6

Travelling Salesman Problem

Answer 6

Given a weighted connected graph G, find the minimum weight Hamiltonian Cycle.

Question 7

Branch-and-bound for TSP

Answer 7

Follow the partial tour given. For the last node in the partial tour, all nodes except the nodes in the partial tour can be visited. For the remaining nodes, nodes not in the subtour and the root node can be visited. The goal is to minimise the cost whenever possible.

The resulting calculation is the bound of a subtour. Terminate the algorithm once it’s clear that the current best cost can’t be improved by visiting other branches.

Question 8

Christofides’ Algorithm

Answer 8

This is an approximation algorithm, with a factor of 1.5, for finding a Minimum Cost Spanning Tree.

1. Find an MST
2. Find the nodes of the tree with odd degrees, and find the matches that have the minimum costs.
3. Perform Euler’s tour.
4. Delete the second instance of a node, as there can only be one instance of each node barring the return to the source.

Question 9

Dijkstra’s Algorithm

Answer 9

Assuming the graph has positive weights, start at the source node. Go to the unvisited nodes, and keep the path with the shortest distance. Repeat until the destination is reached.

Question 10

Triangle Inequality

Answer 10

A complete graph satisfies the triangle inequality if the direct distance between any pair of nodes is less than or equal to the distance of a indirect detour from the first node to the second node.