Approximation Algorithms

1
2
NP-Completeness

Do your best then.

3
 Coping With NP-Hardness
Brute-force Algorithms.
- Develop clever enumeration strategies.
- Guaranteed to find optimal solution.
- No guarantees on the running time.
Heuristics.
- Develop intuitive algorithms.
- Guaranteed to run in polynomial time.
- No guarantees on the quality of solution.
Approximation Algorithms.
- Guaranteed to run in polynomial time.
- Guaranteed to find "high quality" solution, within 1% of optimum.
Obstacle: We need to prove a solution’s value is close to the optimum,
without even knowing what optimum value is! 4
5
 Approximation Algorithms

◼ The best algorithm for solving the NP-complete

problem requires the exponential time in the
worst-case. It is too time-consuming.
◼ To reduce the time required for solving a
problem, we can relax the problem, and obtain
a feasible solution “close” to optimal solution.

6
 Approximation Algorithms

◼ One compromise is to use the “Heuristic“ Solutions.

◼ “Heuristic” may be interpreted as an “Educated Guess”.

◼ Approximation Algorithms return Near Optimal Solutions.

◼ Need to find an Approximation Ratio Bound for algorithm.

7
 Approximation Ratio Bound
We say an approximation algorithm for the problem has a ratio
bound of  (n) if for any input size n, the cost C of the solution

produced by the approximation algorithm is within a factor of

 (n) of the C* of the optimal solution:

C C*
max{ , } =  ( n)
C* C
This applies for both minimization and maximization problems.

8
 Performance Guarantees
◼ An approximation algorithm is bounded
by ρ(n) if, for all input of size n, the
cost c of the solution obtained by an
approximation algorithm is within a
factor ρ(n) of c* of an optimal solution.

9
 -approximation algorithm

◼ An approximation algorithm with an

approximation ratio bound of  is referred
to as -approximation algorithm or also
known as (1+)-approximation algorithm.

◼ Note that  is always > 1 and  =  -1.

10
 Vertex Cover
Vertex Cover: a subset of vertices which “covers” every edge.
An edge is covered if one of its endpoint is chosen.

The Minimum Vertex Cover Problem:

Find a vertex cover with minimum number of vertices.

11
 Vertex Cover Problem
◼ Let G=(V, E). The subset S of V that meets
every edge of E is known as the Vertex Cover.

◼ The Vertex Cover Problem is solved for

finding a vertex cover of the Minimum size. It
is NP-Hard Problem or Optimization Problem
version of an NP-Complete Decision Problem.

12
Examples of Vertex Cover

13
 Vertex Cover Problem
APPROX_VERTEX_COVER(G)
1 C 
2 E'  E( G )
3 while E'  
4 do let ( u, v ) be an arbitrary edge of E'
5 C  C {u, v}
6 remove from E' every edge incident on either u or v
7 return C
14
Vertex Cover Problem
b c d b c d

a e f g a e f g

b c d b c d

a e f g a e f g

b c d b c d

a e f g a e f g

Complexity: O(E)
15
Vertex Cover Problem
Theorem: APPROX_VERTEX_COVER has ratio bound of 2.
Proof. C*: optimal solution
C: approximate solution
A: the set of edges selected in step 4
Let A be the set of selected edges.
| C| = 2| A| When one edge is selected, 2 vertices are added into C.
| A| | C*|
No two edges in A share a common endpoint.
| C|  2| C*|

16
 Traveling Salesperson Problem
Traveling Salesperson Problem (TSP) asks for the shortest
Hamiltonian cycle in a weighted undirected graph.

Consider G be an arbitrary undirected graph with n vertices.

1 if e is an edge in G
Length Function l(e) = { 2 otherwise for Kn
Where, G has a Hamiltonian cycle then there is an
Hamiltonian cycle in Kn whose length is exactly n
Traveling Salesperson Problem is NP-hard (NP-complete) even if all
the edge lengths are 1 or 2 due to polynomial time reduction from
Hamiltonian cycle to this type of Traveling salesperson problem.
17
 Traveling Salesperson Problem
We can replace the values in length function by any values we like
1 if e is an edge in G
{
Length Function l(e) = n otherwise
G has a Hamiltonian cycle then there is an Hamiltonian cycle in Kn
whose length is exactly n or has length at least 2n.
Thus if we can approximate the shortest traveling salesman tour
within a factor of 2 in polynomial time we would have a
polynomial time algorithm for the Hamiltonian cycle problem
For any function f(n) that can be computed in polynomial in n, there is no
polynomial time f(n) approx to TSP on general weighted graph unless P=NP.
18
 TSP: A Special Case
Edge lengths satisfy triangular inequality
l(u,v)  l(u,w) + l(w,v)
This is true for geometric graph

• Compute Minimum Spanning Tree T of the weighted input graph

• Depth First Traversal (Depth First Search) of the MST T
• Numbering the vertices in order that we first encounter them
• Return the cycle found by visiting vertices as per this numbering

19
 TSP: A Special Case
Demonstration

Set of points distributed in 2D

20
 TSP: A Special Case
Demonstration

Minimum Spanning Tree

21
 TSP: A Special Case
Demonstration

Consider this as root

Depth First Traversal

22
 TSP: A Special Case
Demonstration

7 6

1 5

2
3 4
Depth First Traversal and Numbering of Vertices

23
 TSP: A Special Case
Demonstration

7 6

1 5

2
3 4
Traveling Salesperson Tour

24
 TSP: A Special Case
Demonstration

7 6

1 5

3
2
4
Traveling Salesperson Tour with Cost 2.MST

25
 TSP: A Special Case
Demonstration

7 6

1 5

3
2
4
Traveling Salesperson Tour with Reduced Cost  2.MST
26
 TSP: A Special Case
Output Quality :
Cost of the tour using this algorithm
 2* cost of minimum spanning tree
 2* cost of optimal solution

Conclusion: The algorithm outputs 2 approximation of

the minimum traveling salesperson problem

27
 TSP: An Improved Heuristic
Locate odd degree vertices in minimum spanning tree (MST)
7
6

1
5

2
3
4
Number of odd degree vertices is even

28
 TSP: An Improved Heuristic
Locate odd degree vertices in minimum spanning tree (MST)

1
5

2
Perfect matching of odd degree vertices

29
 TSP: An Improved Heuristic
Locate odd degree vertices in minimum spanning tree (MST)

7
6

1
5

2
3 4
Merging the perfect edges with MST
30
 Bin Packing Problem
◼ Given n items of sizes a1, a2, …, an, 0 ai  1 for 1  i  n,
which are to be placed in bins of unit capability, then the
bin packing problem can be solved by determining the
minimum number of bins to accommodate all the items.
◼ Consider the items of different sizes with lengths of time
of executing different jobs on a standard processor, then
we need to use minimum number of processors which can
finish all the jobs within a fixed time. // Assume that the
longest job takes one unit time i.e. equal to fixed time.

31
 Example of Bin Packing Problem
◼ Ex. Given n = 5 items with sizes 0.3, 0.5, 0.8, 0.2, 0.4,
then the Optimal Solution is 3 Bins.

The Bin Packing Problem is NP-Hard Optimization Problem.

32
 An Approximation Algorithm
for the Bin Packing Problem
◼ An Approximation Algorithm: (First-Fit (FF))
place the item i into the lowest-indexed bin
which can accommodate the item i.
◼ OPT: The number of bins of the Optimal Solution
◼ FF: The number of bins in the First-Fit Algorithm
◼ C(Bi): The sum of the sizes of items packed in
the bin Bi in the First-Fit Algorithm
◼ Let FF=m.

33
 An Approximation Algorithm
for the Bin Packing Problem
◼ OPT  , ceiling of sum of sizes of all items
◼ C(Bi) + C(Bi+1)  1 (a)(Otherwise, the items in Bi+1
will be put in Bi). C(Bi): The sum of sizes of items packed in bin Bi
◼ C(B1) + C(Bm)  1 (b)(Otherwise, the items in Bm
will be put in B1. )
◼ For m nonempty bins,
C(B1)+C(B2)+…+C(Bm)  m/2, (a)+(b) for i=1,..,m
m

 FF = m < 2  C( B ) = 2 a  2 OPT
n
i i
i =1 i =1

FF < 2 OPT

34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55