SGT Sheet

Question 1

2. The 2-opt algorithm for TSP Begin by generating a MST of the graph: Graph above is missing $D-E$ but it is considered.

Pre-order traversal: $A,F,D,B,C,E$, cycle is $A,F,D,B,C,E,A$.

Swap $E$ and $D$: 21 -> 4 and 3 -> 10, hence -10.

Swap $B$ and $C$: 21 -> 9 and 5->1, hence -16.

Question 2

Q2.1

$TS{P}_{dec}(G,D)$

1. Go through all Hamiltonian paths
2. There are $n!$ paths to check, this step can be parallelised
3. Checking one path is $O(n)$

Q2.2

This is important, needed for exam!!!

Question 3

This algorithm is polynomial time, [skeptical].