5-IT300 DAA Approximation Algorithms

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 running time.
Heuristics.
Develop intuitive algorithms.
Guaranteed to run in polynomial time.
No guarantees on quality of solution.
Approximation Algorithms.
• Guaranteed to run in polynomial time.
• Guaranteed to find "high quality" solution, say within 1% of optimum.
Obstacle: need to prove a solution’s value is close to optimum,
without even knowing what optimum value is!
4
5
 Up to now, the best algorithm for
solving an NP-complete problem
requires 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 an optimal solution.
6
 One compromise is to use heuristic solutions.
 The word “heuristic” may be interpreted as

“educated guess.”
7
An algorithm that returns near-optimal solutions is called an
Approximation Algorithm.
We need to find an Approximation Ratio Bound for an

approximation algorithm.
8
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.
9
Performance Guarantees
 An approximation algorithm is bounded

by ρ(n) if, for all input of size n, the
cost c of the solution obtained by the
algorithm is within a factor ρ(n) of the
c* of an optimal solution
10
ρ-approximation algorithm
 An approximation algorithm with an

approximation ratio bound of ρ is called
a ρ-approximation algorithm or a (1+ε)-
approximation algorithm.
 Note that ρ is always larger than 1 and

ε=ρ-1.
11
Vertex Cover Problem
 Let G=(V, E). The subset S of V that
meets every edge of E is referred to as
the Vertex Cover.
 The Vertex Cover Problem is solved for
finding a vertex cover of the Minimum
size. It is NP-hard Computational
Problem or the Optimization Version of
an NP-Complete Decision Problem.
12
Examples of Vertex Cover
13
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
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
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
Bin Packing Problem
 Given n items of sizes a1, a2, …, an, 0< ai ≤ 1 for 1
≤ i ≤ n, which have to be placed in bins of unit
capability, the bin packing problem is solved for
determining the minimum number of bins to
accommodate all items.
 If we consider the items of different sizes to be the
lengths of time of executing different jobs on a
standard processor, then the problem becomes to
use minimum number of processors which can
finish all of the jobs within a fixed time. // We can
assume the longest job takes one unit time, which
equals to the fixed time. 17
Example of Bin Packing Problem
 Ex. Given n = 5 items with sizes 0.3, 0.5, 0.8, 0.2, 0.4,
the optimal solution is 3 bins.
The bin packing problem is NP-hard optimization problem.

18
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
bin Bi in the First-Fit Algorithm
 Let FF=m.
19
An Approximation Algorithm
for the Bin Packing Problem
 n 
 OPT ≥  ∑ i ,
aceiling of sum of sizes of all items
 i =1 
 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 n
⇒ FF = m < 2 ∑ C( B ) = 2∑ a ≤ 2 OPT
i =1
i
i =1
i
FF < 2 OPT
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

5-IT300 DAA Approximation Algorithms

Uploaded by

Copyright:

Available Formats

5-IT300 DAA Approximation Algorithms

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5-IT300 DAA Approximation Algorithms

Uploaded by

Copyright:

Available Formats

Approximation Algorithms

 The word “heuristic” may be interpreted as

We need to find an Approximation Ratio Bound for an

produced by the approximation algorithm is within a factor of

 An approximation algorithm is bounded

 An approximation algorithm with an

 Note that ρ is always larger than 1 and

The bin packing problem is NP-hard optimization problem.

You might also like