Week 7 - Travelling salesman problem

Question 1

Whats difference between decision and optimisation problem

Answer 1

Problem Types Summary:

Decision Problem:

Determines if a solution exists.
Returns True or False (yes or no).

Example: “Does a Hamiltonian Cycle exist with total length ≤k?”

Optimization Problem:

Finds the best solution among all possibilities.
Returns the optimal value or solution.

Example: “What is the shortest Hamiltonian Cycle?”
Key Difference:

short answer:
Decision problems focus on existence.
Optimization problems focus on finding the best solution.

Question 1

If i wanted to brute force (deterministic) get the number of distinct hamiltonian cycles how would i do that

use the properties of hamiltonian cycle to build your basis

Answer 1

Hamiltonian cycles: ordering of n vertices so that each vertex visited once and returns to same vertex

Permutations: There are n! ways to order n vertices.

Fix Starting Point: A cycle has no starting point, so fix one vertex → reduces to (𝑛−1)!

Undirected Graph: Traveling in reverse counts as the same cycle → divide by 2. [ A->B same as B->A

Question 2

approximation ratio just read

Answer 2

Approximation Ratio - Key Notes

Definition:
The approximation ratio
𝑅m(w)

Rm(w) measures how close the approximate solution is to the optimal solution.

Formula:
𝑅m(w) = max ((𝐶approx / 𝐶global) , 𝐶global / 𝐶approx)

C approx : Cost of the approximate solution.

C global : Cost of the optimal solution.

Why Both Ratios?
Ensures it works for both minimization (e.g., TSP) and maximization problems.
Guarantees
𝑅𝑀(𝑤)≥1 in all cases

What Does It Mean?

𝑅𝑀(𝑤) = 1 : Approximate solution = Optimal solution.
​
𝑅𝑀(𝑤) > 1 : Approximate solution is worse than the optimal.

Higher 𝑅𝑀(𝑤) : further from optimal
​

Key Insight:
Approximation ratio evaluates how well an algorithm performs compared to the optimal.
Goal: Achieve an approximation ratio as close to 1 as possible.

Question 3

R approbimable

Answer 3

puts a bound on approximation ratio

𝑅𝑀(𝑤) <= R ( approximation ratio cant be greater than R )

for minimisation this means :
Capprox <= R * Cglobal

Question 4

Unapproximable

Answer 4

It is NOT R approximable

we cant put a bound on a poly time approximation algorithm which can give BAD INPUTS that are worse than the bound

Question 5

2 opt algorithm

Answer 5

1) Construct min spanning tree of G ( T0)
2) Do preorder traversal on minimum spanning tree T0
3) DONT FORGET to connect the preorder traversal result to starting vertex to make it a hamiltonian cycle
4) Apply 2 Opt swap until Local optimum

Question 6

proving 2 opt appoximability

Answer 6

disconnect an edge from Hgoblal to make a tree T
-length (T) <= lengh(Hglobal)

. min span tree of T ( min span tree refered to as T0)
- length(T0) <= length(T)

. preorder traversal of min span tree T0 to get H0
- length(H0) <= 2 * length(T0)

. do 2 opt swap until local optimum
- length(Happrox) <= ….<= length(H1) <= length(H0_
- length(Happrox) <= length (Ho)

look at everything affecting Happrox and you see in transitivity you will get length(Happrox) <= 2 * length Hglobal

ie:
length(Happrox) <= length (Ho)
<= 2 * length(T0)
<= 2 * length(T)
<= 2 * length ( Hglobal)

therefore its 2 approximable