Fundamental of optimization

Approximation algorithms

1
CONTENT

• Overview
• Knapsack problem
• TSP problem

2
Overview

• Algorithms with polynomial time complexity

• Find approximate solutions to optimization problems: the distances of the solutions found to optimal
solutions can be probably guaranteed.
• Notation
• Optimal objective value is f*
• Objective value of the solution found by the approximation algorithm is f
• Maximization problems
• We can prove that: f ≥ f* in which  is a positive constant less than 1
• Minimization problems
• We can prove that: f  f* in which  is a positive constant greater than 1

3
KNAPSACK

• There are n items A = {1, 2, . . ., n} in which item i has weight Wi and value Ci (i = 1, 2, …, n). Find a
subset of A such that the sum of weights of items is less than or equal to B and the sum of values is
maximal.
• Let S be a solution to the problem (S is a subset of A). Let f(S) = σ𝑖𝑆 𝐶𝑖 be the value of the solution
S
• Let S* be an optimal solution and f* = f(S*) be the optimal objective value
• Consider 2 algorithms running on 2 sorted list of items:
• Sort in non-increasing order of values
• Sort in non-increasing order of the fractions of values over the weights

4
KNAPSACK

GREEDY-1 () {
({C1, W1}, {C2, W2}, . . ., {Cn, Wn}) is the sorted list in which: C1 ≥ C2 ≥ . . . ≥ Cn;
S = {};
for i = 1 to n do {
if Wi > B then break;
S = S  {i}; B = B – Wi;
}
return S;
}

5
 KNAPSACK

GREEDY-2 () {
𝐶1 𝐶2 𝐶𝑛
({C1, W1}, {C2, W2}, . . ., {Cn, Wn} is the sorted list in which: ≥ ≥...≥ ;
𝑊1 𝑊2 𝑊𝑛
S = {};
for i = 1 to n do {
if Wi > B then break;
S = S  {i}; B = B – Wi;
}
return S;
}

6
KNAPSACK

• There are n items A = {1, 2, . . ., n} in which item i has weight Wi and value Ci (i = 1, 2, …, n). Find a
subset of A such that the sum of weights of items is less than or equal to B and the sum of values is
maximal.
• Approximation algorithms
• Let S1 and S2 be the solutions returned by GREEDY-1 and GREEDY-2
• Notation: f = max{f(S1), f(S2)}
1
• We have f ≥ f*
2

7
KNAPSACK

• Proof
• Consider the linear program below:

f(X) = C1X1 + C2X2 + . . . + CnXn → max

s.t. W1X1 + W2X2 + . . . + WnXn  B
0  X1, X2, . . ., Xn  1

8
KNAPSACK

• Simplex table
X1 X2 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS
W1 W2 ... Wn 1 0 ... 0 0 B
1 0 0 0 1 0 0 1
0 1 ... 0 0 0 ... 0 0 1
… … … … … … … … … …
0 0 1 0 0 1 0 1
-C1 -C2 ... -Cn 0 0 0 0 1 0

9
 KNAPSACK
X1 X2 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS E
R1 W1 W2 ... Wn 1 0 ... 0 0 B B/W1
R2 1 0 0 0 1 0 0 1 1
R3 0 1 ... 0 0 0 ... 0 0 1 
… … … … … … … … … …
Rn+1 0 0 1 0 0 1 0 1 
Rn+2 -C1 -C2 ... -Cn 0 0 0 0 1 0

Select column 1, suppose B ≥ W1 → select row R2: R1 = R1 – W1R2; Rn+2 = Rn+2 + C1R2

X1 X2 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS E

R1 0 W2 ... Wn 1 -W1 ... 0 0 B-W1
R2 1 0 0 0 1 0 0 1
R3 0 1 ... 0 0 0 ... 0 0 1
… … … … … … … … … …
Rn+1 0 0 1 0 0 1 0 1
Rn+2 0 -C2 ... -Cn 0 C1 0 0 1 C1

10
 KNAPSACK
X1 X2 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS E
R1 0 W2 ... Wn 1 -W1 ... 0 0 B-W1 (B-W1)/W2
R2 1 0 0 0 1 0 0 1 
R3 0 1 ... 0 0 0 ... 0 0 1 1
… … … … … … … … … … ...
Rn+1 0 0 1 0 0 1 0 1 
Rn+2 0 -C2 ... -Cn 0 0 0 0 1 C1

Select column 2, Suppose (B–W1) ≥ W2 → select row R3: R1 = R1 – W2R3; Rn+2 = Rn+2 + C2R3

X1 X2 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS E

R1 0 0 ... Wn 1 -W1 ... 0 0 B - W1 –W2
R2 1 0 0 0 1 0 0 1
R3 0 1 ... 0 0 0 ... 0 0 1
… … … … … … … … … …
Rn+1 0 0 1 0 0 1 0 1
Rn+2 0 0 ... -Cn 0 C1 C2 0 1 C1 + C2

11
 KNAPSACK
X1 X2 X3 ... Xn Xn+1 Xn+2 ... X2n+1 Z RHS E
R1 0 0 W3 ... Wn 1 -W1 ... 0 0 B - W1 –W2 (B - W1 –W2) / W3
R2 1 0 0 ... 0 0 1 0 0 1 
R3 0 1 0 ... 0 0 0 ... 0 0 1 
R4 0 0 1 ... 0 0 0 … … … 1 1
Rn+1 0 0 0 ... 1 0 0 1 … … 
Rn+2 0 0 -C3 ... -Cn 0 C1 C2 0 1 C1 + C2

Select column 3, suppose (B–W1 - W2) < W3 → select row R1: R1 = R1/W3; Rn+2 = Rn+2 + C3R1/W3

X1 X2 X3 X4 … Xn Xn+1 Xn+2 ... X2n+1 Z RHS

R1 0 0 1 W4/W3 … Wn/W3 1 -W1 ... 0 0 (B-W1 –W2)/W3
R2 1 0 0 0 … 0 0 1 0 0 1
R3 0 1 0 0 … 0 0 0 ... 0 0 1
R4 0 0 0 -W4/W3 … -Wn/W3 0 0 … … … …
Rn+1 .. .. .. ... … 1 0 0 1 0 1
Rn+2
0 0 0 -C4+W4*C3/W3 … -Cn+Wn*C3/W3 0 C1 C2 0 1 C1 + C2

12
 KNAPSACK
X1 X2 X3 X4 … Xn Xn+1 Xn+2 ... X2n+1 Z RHS
R1 0 0 1 W4/W3 … Wn/W3 1 -W1 ... 0 0 (B-W1 –W2)/W3
R2 1 0 0 0 … 0 0 1 0 0 1
R3 0 1 0 0 … 0 0 0 ... 0 0 1
R4 0 0 0 -W4/W3 … -Wn/W3 0 0 … … … …
Rn+1 .. .. .. ... … 1 0 0 1 0 1
Rn+2 0 0 0 -C4+W4*C3/W3 … -Cn+Wn*C3/W3 0 C1 C2 0 1 C1 + C2

• Values of the last row are non-negative, the table corresponds to an optimal solution: X1 = 1, X2 =
1, X3 = (B-W1-W2)/W3, X4 = … = Xn = 0.
• Generality: select column from left to right (from columns 1, 2, 3, . . . ). Suppose k is the first index
(iteration) where B-W1-W2-. . .-Wk-1 < Wk. An optimal solution to the linear problem is: X1 = X2 = . . .
= Xk-1 = 1., Xk = (B-W1-W2-. . .-Wk-1)/Wk, Xk+1 = . . . = Xn = 0 optimal objective value is C1 + C2 + . . . +
Ck, với  = (B-W1-W2-. . .-Wk-1)/Wk , ( < 1)

13
BÀI TOÁN KNAPSACK

• The given linear program is a relaxation of the original Knapsack problem: optimal objective value
of the Knapsack problem is f*  C1 + C2 + . . . + Ck. Objective value of the solution returned by the
approximation is f(S1) = C1 + C2 + . . . + Ck-1.
• We have f*  C1 + C2 + . . . + Ck < C1 + C2 + . . . + Ck-1 + Ck = f(S1) + Ck. Therefore, f(S1) > f*/2 or f(S2)
≥ Ck > f*/2.
• Hence f = max{f(S1), f(S2)} > f*/2.

14
TRAVELLING SALESMAN PROBLEM - TSP

• Let G = (V, E) be a complete graph in which V = {1, 2, . . ., n} is the set of nodes. Edge (u,v) has
weight c(u,v). Find the Hamilton cycle G such that the total weights is minimal.
• Approximation algorithm:
• Let T(G) be a minimum spanning tree of G.
• Duplicate the edges of T → we obtain an Euler graph with the Euler cycle E(T).
• Let S0 be the sequence (pairwise distinct) of nodes visited when travelling along E(T). The
addition of the first node of S0 to the end of S0 yields a Hamilton cycle S which is the solution
of the approximation algorithm.
• Example 2 2
• E(T) = 1, 2, 1, 5, 1, 3, 4, 3, 1 1 1
• S0 = 1, 2, 5, 3, 4
• S = 1, 2, 5, 3, 4, 1 3 3

5 5
4 4

15
THANK YOU !

16