Approximation Algorithms

Pasi Fränti
16.9.2020
 Approximation algorithms

• Optimal algorithm too slow

• Heuristic algorithm too uncertain
• Provide result with guarantee:
f OPT  f

f OPT
f  result of approximation algorithm
f OPT  result of optimal algorithm
 Bin packing problem

• Consider a set of bins (capacity 1) and

a set of items xi of size wi[0,1].
• GOAL: pack the items into as few bins as
possible
• Finding the optimal solution is a NP-hard
problem (exponential time)
 Bin packing example
Greedy algorithm
Items: [0.4, 0.7, 0.5, 0.2, 0.9, 0.6]

0.2
0.5
1.0 0.9
0.4 0.7 0.6

w i  f OPT  f  2   wi
o n
t i
 f  f OPT  2   wi   wi   wi im m
a !
o x h
t

f  f OPT

 w i
1 -
p
a lg
r
p o ri

f OPT w i
1 a
 Traveling Salesman Problem

• ASSUMPTION: All pairwise distances exist

and they obey triangular inequality:
w(a,c) ≤ w(a,b)+w(b,c)
• GOAL: find the shortest possible route that
visits each city once and returns to the
origin city
• Finding optimal route is slow (NP-hard)
 Double tree algorithm
TSP-doubletree(V, E)
T  MST(V, E);
R  WALK-OF-TREE(T); //depth-first
 A-B-C-B-H-B-A-D-E-F-E-G-E-D-A
S  SHORTCUTS(R); // skip redundant
 A-B-C-H-D-E-F-G-A

A D
E

B F G

C
H
Algorithm example
Graph with N=8 nodes

A D

B F G

H
 Algorithm example
Minimum spanning tree

2
A D

11.9 2
2
E
2 2

B F G

2
5
C

H
 Algorithm example
Tree traversal
2
A D
2 2
23.8
2 2 2
E
2 2
2 2
B F G
2
5
2
C
5

H
A-B-C-B-H-B-A-D-E-F-E-G-E-D-A
 Algorithm example
Shortcuts

A D

19.1
20 2
2
E
2
17
B F G
2 2

5
H
A-B-C-B-H-B-A-D-E-F-E-G-E-D-A
 Algorithm example
Final result

A D

19.1
E

B F G

H
A-B-C-H-D-E-F-G-A
 Analysis of error bound
1-approximation algorithm

Tree traversal includes all edges twice:

f  f R  2  f MST
Cutting one link from TSP is spanning tree,
but not necessarily the minimum:
f MST  fTSP
Tree traversal includes all edges twice:

 f  2  f MST  2  fTSP
fTSP  f fTSP  2  fTSP
  1  1
fTSP f TSP
 Christofides algorithm

Christofides(V, E)
T  MST(V, E);
Find Euler tour:
D  FindOddNodes(T);
M  PerfectMatch(D);
H  T+M;
R  EulerTour(H);
S  SHORTCUTS(R);
 Christofides example
Minimum spanning tree

2
A D

11.9 2
2
E
2 2

B F G

2
5
C

H
 Christofides example
Detect the nodes with odd degree

A D

B F G

H
Christofides example
Matching the nodes

A D

2

B F G

2
5
C

H
Christofides example
Merging MST and the matching

A D

B F G

H
 Christofides example
Euler tour

2
A D

17.0 2
2
E
2 2
2
B F G

2
2 5 5
C

H
A-B-C-B-H-F-E-G-E-D-A
 Christofides example
Shortcuts

2
A D

15.5 2∙2
2
E

2
2
B F G

2
5
C
5
H
A-B-C-B-H-F-E-G-E-D-A
Christofides example
Shortcuts

A D

B F G

H
 Error bounds for Christofides
MST + Matching

Christofides produces TSP which is at most 50%

longer than the optimum:
f  1.5  f OPT
Proof: The algorithm combines MST with the minimum-
weight perfect matching:

f  f MST  f Match
Shortcuts can only shorten the tour.
 Error bounds for Christofides
Links from matching
Let v1, v2, …, v2m be the odd nodes of T.
Skipping the rest of the nodes in TSP
gives path that consists of two matchings:
M1 ={(v1, v2), …, (v2m-1, v2m)}
M2 ={(v2, v3), …, (v2m, v1)} Odd nodes

Due to optimality of matching:

TSP
2  f Match  f M 1  f M 2  fTSP
v1 v2
 f Match  0.5  fTSP v2m v3

v4
Links complementing tour v2m-1
Links from matching …
 Error bounds for Christofides
0.5-approximation algorithm

Cutting one link from TSP is spanning tree,

but not necessarily the minimum:
f MST  f TSP

Combining this with the matching:

f  f MST  f Match  fTSP  0.5  fTSP  1.5  fTSP

Thus we have:
fTSP  f fTSP  1.5  fTSP
   0 .5   0 .5
fTSP fTSP
Empty space for notes
 Pseudo polynomial knapsack

Input: Weight of N items {w1, w2, ..., wn}

Cost of N items {c1, c2, ..., cn}
Knapsack limit s
Goal: Select for knapsack: {x1,x2,…xn} so that
n n

w x i i s c  x
i 1
i i  max!
i 1

• Problem is NP hard
• Pseudo polynomial solution exist
• Used for approximation algorithm
 Pseudo polynomial knapsack
Dynamic programming algorithm

KNAPSACK (c[1,n], w[1,n], s} RETURNS x[1,n]

R  {(∅,0)} Include if If same cost prune
item fits in out weaker solution
FOR i 1 TO n DO
FOR (S,c)  R DO
IF ΣjS wj+wi ≤ s THEN R  R∪{(S∪{i},c+ci)}
FOR (S,c), (S’,c)  R DO

Ne mb
IF ΣjS wj ≤ ΣjS’ wj THEN R  R\{(S’,c)}

co
w y
ELSE R  R\{(S,c)}
(S,c)  (S,c’)R for which c’ is max!
FOR i1 TO n DO IF iS THEN x[i]1 ELSE x[i]0
RETURN x;
 Pseudo polynomial knapsack
Time complexity

Sample input:
wi={1,1,2,4,12}
ci ={1,2,2,10,4}
s=15
All combinations:
∅ {1} {2} {1,2} {3} {1,3} {2,3} {1,2,3} …
1 2 3
Time complexity:
O(nc) where c = cost of optimal solution
…but c  O ( 2 )
n
 Approximation algorithm
Scaling the input

Scale
Original input: down Modified input:
input
c1 c2 c3  cn c1 c2 c3 cn

d d d d
Solve by DP Solve by DP

y1 y2 y3  yn x1 x2 x3  xn

wi ={1,1,2,4,12} wi ={1,1,2,4,12}
ci ={2,3,3,10,4} [ci/d] ={1,1,1,5,2}
S =15 S =15
 Approximation algorithm
Error bound
Optimal Optimal
for original for scaled ∙ d/d

ci
c   ci yi   ci xi  d   xi
d
Truncate xi optimal for scaled
 ci   ci 
 d     xi  d     yi and thus bigger

d  d 
z ≥ z-1
 ci 
 d     1 yi    ci  d  yi
d 
  ci yi   dyi  c  nd
=c Σyi≤
n
 Approximation algorithm
nd/c-approximation algorithm

Result of algorithm: f   ci xi

Optimal result: f opt  c Re

vis
e
f opt  f c   c  nd  nd
  
f opt c c
• Choosing d = ε∙c/n, we can get any ε-approximation
• Value c is not known but upper limited: c ≤ n∙c max
• Time complexity: T  n   nc d  n   n 
2 3

Note:  0  1 
Empty space for notes

A
1 B
2 C
4 D
3
4 3 1
E F
?
 Acknowledgements

Contributions by Sharon Guardado and Pekka T.

Kilpeläinen to TSP example and its proof appreciated.