Approximation Algorithms
Dr. Navjot Singh
Design and Analysis of Algorithms
Approximation Algorithms
⚫ Motivation:
⚫ Many problems are NP-complete, so unlikely find efficient algorithms
⚫ Three ways to get around:
⚫ If input size is small, exponential algorithm is OK.
⚫ Isolate important special case and find poly algorithms for them.
⚫ Find near-optimal solutions in poly time.
⚫ So approximate algorithms:
⚫ An algorithm that returns near-optimal solutions in polynomial time
2
Approximation Algorithms (cont)
⚫ Approximation Ratio ρ(n):
⚫ Define: C* as a optimal solution and C is the solution produced by
the approximation algorithm
⚫ ρ(n) = max (C/C*, C*/C)
⚫ Maximization problem: 0 < C <= C*, thus C*/C shows that C* is
larger than C by ρ(n)
⚫ Minimization problem: 0 < C* <= C, thus C/C* shows that C is larger
than C* by ρ(n)
⚫ If (n)=1, then the algorithm is optimal
⚫ The larger (n), the worse the algorithm
3
Approximation Algorithms (cont)
⚫ PTAS (Polynomial Time Approximation Scheme): A (1 + ε)-
approximation algorithm for a NP-hard optimization problem
where its running time is bounded by a polynomial in the size
n of the input instance, O(nf(1/ε)).
⚫ The running time of a polynomial-time approximation scheme can
increase very rapidly as ε decreases. For example, the running time
of a polynomial-time approximation scheme might be O(n2/ε).
⚫ Ideally, if ε decreases by a constant factor, the running time to
achieve the desired approximation should not increase by more than
a constant factor (though not necessarily the same constant factor
by which ε decreased). 4
Approximation Algorithms (cont)
⚫ PTAS (Polynomial Time Approximation Scheme): A (1 + ε)-
approximation algorithm for a NP-hard optimization problem
where its running time is bounded by a polynomial in the size
n of the input instance, O(nf(1/ε)).
⚫ O(nf(1/ε)) – polynomial in n, may be exponential in 1/ε.
⚫ Accuracy - Good for large ε, slow for small ε.
⚫ Example - Euclidean Travelling Salesman Problem
5
Approximation Algorithms (cont)
⚫ FPTAS (Fully PTAS): The same as above + time is bounded
by a polynomial in both the size n of the input instance and
1/ε.
⚫ For example, the scheme might have a running time of O((1/ε)2n3).
⚫ With such a scheme, any constant-factor decrease in ε comes with a
corresponding constant-factor increase in the running time.
⚫ O(nc(1/ε)d) – polynomial in n and 1/ε.
⚫ Accuracy - Very fast, even for very small ε.
⚫ Example - 0-1 Knapsack, Subset Sum
6
Vertex-cover problem
⚫ Vertex cover: given an undirected graph G=(V,E), then a
subset V'V such that if (u,v)E, then uV' or v V' (or both).
⚫ Size of a vertex cover: the number of vertices in it.
⚫ Vertex-cover problem: find a vertex-cover of minimal size.
7
Vertex-cover problem (cont)
O(V+E) using adjacency lists to represent E’
8
9
2-approximate vertex-cover
⚫ Theorem: APPROXIMATE-VERTEX-COVER is a poly time 2-approximate
algorithm, i.e., the size of the returned vertex cover set is at most twice the size
of optimal vertex-cover.
⚫ Proof:
⚫ It runs in polynomial time.
⚫ The returned C is a vertex-cover.
⚫ Let A be the set of edges picked in line 4 and C* be the optimal vertex cover.
⚫ Then C* must include at least one end of each edge in A and no two edges in A are
covered by the same vertex in C*, so |C*||A|.
⚫ Moreover, |C|=2|A|, so |C|2|C*|.
10
Travelling-Salesman problem (TSP)
⚫ Let’s model the problem as a complete graph with n vertices,
so that the salesperson wishes to make a tour or Hamiltonian
cycle, visiting each city exactly once and finishing at the
starting city.
⚫ The salesperson incurs a nonnegative integer cost c(i, j) to
travel from city i to city j.
⚫ In the optimization version of the problem, the salesperson
wishes to make the tour whose total cost is minimum, where
the total cost is the sum of the individual costs along the
edges of the tour. 11
Travelling-Salesman problem (cont)
APPROX-TSP-TOUR is (V2)
12
13
2-approximate TSP
⚫ Theorem: When the triangle inequality holds, APPROX-TSP-TOUR is a
polynomial-time 2-approximation algorithm for the traveling-salesperson problem.
⚫ Proof:
⚫ It runs in polynomial time.
⚫ Let H* denote an optimal tour for the given set of vertices.
⚫ Deleting any edge from a tour yields a spanning tree, and each edge cost is
nonnegative.
⚫ Therefore, the weight of the minimum spanning tree T computed in line 2 of
APPROX-TSP-TOUR provides a lower bound on the cost of an optimal tour:
c(T) ≤ c(H*)
14
2-approximate TSP (cont)
⚫ Theorem: When the triangle inequality holds, APPROX-TSP-TOUR is a
polynomial-time 2-approximation algorithm for the traveling-salesperson problem.
⚫ Proof:
⚫ A full walk of T lists the vertices when they are first visited and also whenever
they are returned to after a visit to a subtree. Let’s call this full walk W. The full
walk of our example gives the order
a, b, c, b, h, b, a, d, e, f, e, g, e, d, a
⚫ Since the full walk traverses every edge of T exactly twice, by extending the
definition of the cost c in the natural manner to handle multisets of edges, we
have
c(W) = 2c(T) and hence c(W) ≤ 2c(H*) 15
2-approximate TSP (cont)
⚫ Theorem: When the triangle inequality holds, APPROX-TSP-TOUR is a
polynomial-time 2-approximation algorithm for the traveling-salesperson problem.
⚫ Proof:
⚫ Of course, the full walk W is not a tour, since it visits some vertices more than
once.
⚫ By the triangle inequality, however, deleting a visit to any vertex from W does
not increase the cost.
⚫ When a vertex v is deleted from W between visits to u and w, the resulting
ordering specifies going directly from u to w.
⚫ Repeatedly applying this operation on each visit to a vertex after the first time
it’s visited in W, so that W is left with only the first visit to each vertex. 16
2-approximate TSP (cont)
⚫ Theorem: When the triangle inequality holds, APPROX-TSP-TOUR is a
polynomial-time 2-approximation algorithm for the traveling-salesperson problem.
⚫ Proof:
⚫ In the example, this process leaves the ordering a, b, c, h, d, e, f, g.
⚫ This ordering is the same as that obtained by a preorder walk of the tree T.
⚫ Let H be the cycle corresponding to this preorder walk. It is a hamiltonian
cycle, since every vertex is visited exactly once, and it is the cycle computed
by APPROX-TSP-TOUR.
⚫ Since H is obtained by deleting vertices from the full walk W, we have
c(H) ≤ c(W) and hence c(H) ≤ 2c(H*),
which completes the proof. 17
Subset-Sum Problem
⚫ An instance of the subset-sum problem is given by a pair (S, t),
where S is a set {x1, x2, …, xn} of positive integers and t is a positive
integer. This decision problem asks whether there exists a subset of
S that adds up exactly to the target value t.
⚫ This problem is NP-complete.
18
Subset-Sum Problem (contd.)
19
Subset-Sum Problem (contd.)
20
Subset-Sum Problem (contd.)
21
22
Subset-Sum Problem (contd.)
APPROX-SUBSET-SUM is a fully polynomial-time approximation scheme for the
subset-sum problem.
23
24
Subset-Sum Problem (contd.)
25
Acknowledgements
⚫ Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.,
Introduction to algorithms. MIT press, 2009
⚫ Dr. David Kauchak, Pomona College
⚫ Prof. David Plaisted, The University of North Carolina at Chapel
Hill
26