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.