CSC373H Lecture 11
Dan Zingaro
November 28, 2016
Traveling-Salesman Problem (TSP)
Wehaveacomplete,undirectedgraphG=(V,E),witha nonnegative integer cost c(u, v) for each edge (u, v)
The traveling-salesman problem (TSP) is to find a minimum-cost “tour” in the graph that starts at some vertex v, hits every other vertex exactly once, and then returns to v
“Salesman”, because it’s like a salesman starting from home, visiting every city once, and returning home
We assume that c satisfies the triangle inequality: c(u, w) ≤ c(u, v) + c(v, w)
The TSP is NP-complete (even with the triangle inequality)
MST Algorithm for TSP
Here is an MST-based approximation algorithm that produces a TSP tour that is no worse than twice the optimal TSP tour.
select r to be root vertex
grow an MST T from r (use Prim’s alg)
let H be the order of nodes reached in a
preorder traversal of T
return H
TSP: Example
What is the optimal TSP tour in this graph?
a
1
b1
23
2c
2
d
One possible MST is below.
a
11
bc
2
d
MST Algorithm: Approximation Ratio Proof
Let H∗ be an optimal TSP tour
If we take H∗ and remove one edge, we get a spanning tree
Remember that each edge cost in the graph is assumed to be nonnegative
Therefore, all spanning trees, including MST T, have lower cost than the optimal TSP tour H∗
Wehavec(T)≤c(H∗)
MST Algorithm: Approximation Ratio Proof…
A full walk of a tree T lists the vertices when they are first visited and also when returned to after a visit to a subtree
LetW beafullwalkofT e.g. a,b,a,c,d,c,a
The full walk traverses each edge exactly twice, so we have c(W) = 2c(T)
Using both equations gives us c(W) ≤ 2c(H∗)
MST Algorithm: Approximation Ratio Proof…
However, W is not a valid TSP tour; it visits some vertices multiple times
By the triangle inequality, we can delete any vertex without making the cost of W worse
Deleting all visits to vertices from W except the first visit to each vertex yields a tour H
We have c(H) ≤ c(W) ≤ 2c(H∗)
Minimum Cut Problem
Input:undirectedgraphG=(V,E)withmedgesandn vertices, and where parallel edges are allowed
Cut: grouping of all vertices into two nonempty, nonoverlapping subsets
An edge crosses cut (A,B) if one endpoint of the edge is in A and the other endpoint is in B
Goal: compute the cut such that the number of edges crossing the cut is minimal (min cut)
There are an exponential number of cuts, so brute-force isn’t feasible
Randomized Contraction Algorithm
Karger’s algorithm is a randomized algorithm for the min-cut problem.
On each iteration, we choose an edge (u,v) uniformly at random and fuse u and v into a single supervertex
This can create parallel edges, which we will allow
It also may create self-loops, which we will delete
Each iteration therefore reduces the number of vertices by 1
The algorithm terminates when we have 2 vertices remaining
The two remaining vertices represent a cut in the original graph
Sample graph
Karger’s algorithm is randomized, so there are many possible executions! Let’s look at two . . .
Execution 1
Contract edge (a,c)
Remove the self-loop
Execution 1…
Contract edge (ac,d)
Remove the self-loop
The cut returned is (acd,b)
2 edges cross this cut
This happens to be the min cut.
Execution 2
Contract edge (a, b)
Remove the self-loop
Execution 2…
Contract edge (c,d)
Remove the self-loop
The cut returned is (ab,cd) 3 edges cross this cut
This is not the min cut
Notation
Let(A,B)beamincut
We say that the algorithm is correct iff it outputs this minimum cut
The graph may have multiple minimum cuts, but we are choosing just one of them
Let k be the number of edges that cross (A,B)
LetF bethesetofthesek edges
Good and Bad Choices
What happens when the algorithm chooses to contract an edge in F?
It results in a vertex from A and a vertex from B being fused into a single supervertex
The algorithm will therefore not return (A, B )
What happens when the algorithm chooses to contract an edge not in F?
It fuses two vertices that are both in A or both in B
The algorithm might therefore return (A,B)
Conclusion: probability of success is the probability that the algorithm never contracts an edge of F
Probability of Success
Let s(i) denote the event of contracting an edge of F in iteration i
The success probability is the probability that none of these events happens:
s(1) ∩ s(2) ∩ . . . ∩ s(n − 2)
Probability of Success: First Iteration
What is s(1)?
k edges cross the cut
There are m edges in total
Sop(s(1))=k/m
We don’t know how m changes on each iteration, but we do know exactly how n changes
n decreases by 1 on each iteration
Let’s rewrite this probability using n instead of m
Probability of Success: First Iteration…
Observation 1: in original graph G, the degree d(u) of any vertex u is at least k
Proof: otherwise, for some vertex u, the cut (u, V − u) would have fewer than k crossing edges
Observation 2: for any undirected graph, we have v∈V d(v) = 2m
kn ≤ d(v) v∈V
= 2m This can be rearranged as m ≥ kn/2
Probability of Success: First Iteration…
Let’s now use the fact that m ≥ kn/2 to rewrite p(s(1)) in terms of n
p(s(1)) = k/m
≤ k/(kn/2)
= 2/n
So, p(s(1)) ≥ 1 − 2/n
Probability of Success: Second Iteration
What is p(s(1) ∩ s(2))?
p(s(1) ∩ s(2))
= p(s(2)|s(1)) ∗ p(s(1))
= p(s(2)|s(1)) ∗ (1 − 2/n)
≥ (1 − k/(remaining edges)) ∗ (1 − 2/n)
≥ (1−k/(k(n−1)/2))∗(1−2/n)
(as m ≥ k(n − 1)/2)
= (1−2/(n−1))∗(1−2/n)
Probability of Success: In General
Now we extend the pattern to the n − 2 iterations of the algorithm. (1 − 2/n) ∗ (1 − 2/(n − 1)) ∗ (1 − 2/(n − 2)) ∗ (1 − 2/(n − 3)) ∗ …∗(1−2/4)∗(1−2/3)
= (n − 2)/n ∗ (n − 3)/(n − 1) ∗ (n − 4)/(n − 2) ∗ (n − 5)/(n − 3)∗ …∗2/4∗1/3
= 2/(n(n − 1)) ≥ 1/n2
Not so Good?
So, the algorithm has a 1/n2 probability of returning the min cut (A,B)
Opinion 1: this is a low probability! The algorithm is no good!
Opinion 2: this is polynomial. Maybe we can improve it further?
Idea: boost the success probability using repeated trials
Run the algorithm multiple times, keeping the best min cut
that it returns
How many times should we run it?
Boosting the Success Probability
Probability that a single trial fails is at most 1 − 1/n2
With repeated trials, we succeed if even one trial succeeds
Probability of all N independent trials failing is at most (1 − 1/n2)N
Question: what should we use for N?
Boosting the Success Probability…
For all x, we have the inequality 1 + x ≤ ex Let N = n2
(1−1/n2)n2 ≤(e−1/n2)n2 (fromaboveinequality) = (e−1/n2∗n2)
= e−1 = 1/e
This is down to a 1/e failure probability now!
Boosting the Success Probability…
Let’s keep boosting
Instead of doing n2 trials, let’s do n2 ln n trials
(1 − 1/n2)n2 ln n ≤ (e−1/n2 )n2 ln n (using the inequality) = e− ln n
= 1/eln n = 1/n
Lessons
We started with a “bad” success probability 1/n2 . . . but it is only “polynomially bad”
We used repeated trials to boost this to a 1 − 1/n = (n − 1)/n success probability
This material is based on the presentation in Kleinberg and Tardos. Algorithm Design. 2005.