Design and Analysis of Algorithms
Lectures 36
(Polynomial-time Approximation Algorithms)
Partha Sarathi Mandal
Dept. of Mathematics, IIT Guwahati
Good Approximation Ratios
• Can we achieve 𝜌 = 1 ± ϵ with ϵ as small as we like?
• In certain cases, we can.
1
• Running time becomes a function of 𝑛 and
ϵ
1
• 𝑂(𝑛1/ϵ ) is polynomial in 𝑛 if ϵ is constant, but not so if ϵ is
log 𝑛
or 1/n
3 1
• 𝑂(𝑛 ൗϵ2 ) is polynomial in both 𝑛 and
ϵ
• Definition: Let 𝐴 be a 1 ± ϵ -approximation algorithm.
– A is called a polynomial-time approximation scheme (PTAS) if
its running time is polynomial in 𝑛
– A is called a fully polynomial-time approximation scheme
(FPTAS) if its running time is polynomial in 𝑛 and 1/ϵ.
0-1 Knapsack Problem
• We have 𝑛 objects 𝑂1, 𝑂2, … , 𝑂𝑛.
• 𝑂𝑖 has weight 𝑤𝑖 and value (profit) 𝑝𝑖.
• Assume that 𝑤𝑖 and 𝑝𝑖 are positive integers.
• There is a knapsack of capacity 𝐶 (positive integer)
• Goal: To pack a sub-collection 𝑂𝑖1 , 𝑂𝑖2 , … , 𝑂𝑖𝑚 of the given
objects in the knapsack such that:
– The profit 𝑝𝑖1 + 𝑝𝑖2 + ⋯ + 𝑝𝑖𝑚 of the packed objects is maximized,
and
– 𝑤𝑖1 + 𝑤𝑖2 + ⋯ + 𝑤𝑖𝑚 ≤ 𝐶.
• We may assume that each 𝑤𝑖 ≤ 𝐶 (discard objects that do not
fit individually in the knapsack)
• Obvious greedy strategies “most profitable first” and “maximum
profit/weight first” lead to arbitrarily bad solutions.
A Dynamic-Programming
Algorithm for 0-1 KNAPSAC
• Let 𝑃 = 𝑝1 + 𝑝2 + ⋯ + 𝑝𝑛 . We populate an 𝑛. 𝑃 table 𝑇
• For 1 ≤ i ≤ 𝑛 and 1 ≤ p ≤ 𝑃, the entry 𝑇(𝑖, 𝑝) stores the weight of a lightest
sub-collection 𝑂1, 𝑂2, … , 𝑂𝑖, whose profit is exactly 𝑝.
• If the profit 𝑝 is not achievable by any sub-collection, we store 𝑇 𝑖, 𝑝 = ∞.
𝑤 if 𝑝 = 𝑝1
• Initialize the first row: 𝑇 1, 𝑝 = ቊ 1
∞ otherwise
𝑇 𝑖 − 1, 𝑝 if 𝑝𝑖 > 𝑝
• For 𝑖 > 1, we have 𝑇 𝑖, 𝑝 = ൞min 𝑤𝑖, 𝑇 𝑖 − 1, 𝑝 if 𝑝𝑖 = 𝑝
min 𝑤𝑖, 𝑇 𝑖 − 1, 𝑝 − 𝑝𝑖 , 𝑇 𝑖 − 1, 𝑝 if 𝑝𝑖 < 𝑝
•
• The maximum profit is min1≤p≤𝑃 𝑝|𝑇(𝑛, 𝑝) ≤ 𝐶 .
Running Time
• First suppose that the weight and profits are single-
precision integers.
• Let if 𝑝𝑚𝑎𝑥 = max 𝑝1, 𝑝2, … , 𝑝𝑛 , so 𝑃 ≤ 𝑛𝑝𝑚𝑎𝑥
• Each entry 𝑇(𝑖, 𝑝) can be stored 𝑂 log 𝑛 bits/words
• There are n𝑃 ≤ 𝑛2𝑝𝑚𝑎𝑥 entries in 𝑇, table
• The total running time is therefore 𝑂(𝑛2𝑝𝑚𝑎𝑥log 𝑛).
• Now allow 𝑝𝑖 to be arbitrarily large
• If 2l-1 ≤ 𝑝𝑚𝑎𝑥<2l each profit can be stored using l bits.
• The input size is 𝑂 𝑛𝑙
• The running time is polynomial in 𝑛 but exponential in 𝑙
An FPTAS for 0-1 KNAPSACK
• Take a constant σ
• Consider the scaled-down profits 𝑝𝑖′ = 𝑝𝑖 /σ
• Run the dynamic-programming algorithm with the original
weights and the scaled-down profits.
• Since the weights are not changed, the capacity constraint is
satisfied.
• Suppose that the algorithm returns the scaled-down total profit
𝑆𝑂𝑃𝑇 ′ . This is optimal with respect to the scaled-down item
profits 𝑝𝑖′
• We pack the same objects that achieve 𝑆𝑂𝑃𝑇𝑖′ but consider the
original profit values of the objects. Call this total profit S𝑂𝑃𝑇
• Let 𝑂𝑃𝑇 be the optimal total profit with the original 𝑝𝑖
• Let 𝑂𝑃𝑇 ′ be the scaled-down total profit of the objects that
achieve 𝑂𝑃𝑇.
• We want S𝑂𝑃𝑇 ≥ 1 − 𝜖 𝑂𝑃𝑇
Determination of σ
𝑝
• 𝑝𝑖′ = 𝑝𝑖/σ ⇒ 𝑝𝑖′ ≥ 𝑖 − 1 ⇒ σ𝑝𝑖′ = 𝑝𝑖 − σ ⇒ 𝑝𝑖 − σ𝑝𝑖′ ≤ σ.
σ
• Sum over all (say, 𝑘) objects corresponding to 𝑂𝑃𝑇:
𝑂𝑃𝑇 − σ𝑂𝑃𝑇 ′ ≤ 𝑘σ ≤ nσ.
𝑝
• 𝑝𝑖′ = 𝑝𝑖/σ ≤ 𝑖 ⇒ σ𝑝𝑖′ ≤ 𝑝𝑖
σ
• Sum over all objects corresponding to 𝑆𝑂𝑃𝑇 ′ : σ𝑆𝑂𝑃𝑇 ′ ≤ 𝑆𝑂𝑃𝑇.
• 𝑆𝑂𝑃𝑇 ′ is optimal for the scaled-down profits: 𝑆𝑂𝑃𝑇 ′ ≥ 𝑂𝑃𝑇 ′
• We have 𝑆𝑂𝑃𝑇 ≥ σ𝑆𝑂𝑃𝑇 ′ ≥ σ𝑂𝑃𝑇 ′ ≥ 𝑂𝑃𝑇 − 𝑛σ
• We want 𝑆𝑂𝑃𝑇 ≥ (1 − ϵ)OPT
𝑂𝑃𝑇
• This is fulfilled by any σ satisfying σ ≤ 𝜖.
𝑛
𝑝𝑚𝑎𝑥
• Since pmax ≤ 𝑂𝑃𝑇, we take σ = 𝜖.
𝑛
Running Time
• The dynamic programming algorithm with
scaled-down profits runs in 𝑂(𝑛2𝑝′𝑚𝑎𝑥log 𝑛).
𝑝𝑚𝑎𝑥 𝑛 𝑝𝑚𝑎𝑥
• 𝑝′𝑚𝑎𝑥 = 𝑝𝑚𝑎𝑥/σ ≤ = since σ= 𝜖.
σ 𝜖 𝑛
𝑛3 log 𝑛
• So the running time is 𝑂( ).
∈
• This is polynomial in both 𝑛 and 1/𝜖
• So, this is an FPTAS for the 0-1 knapsack
problem.