程序代写代做代考 algorithm CSC373H Lecture 11

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.