Approximation Algorithms Part Three: (F)PTAS

Advanced Algorithms – COMS31900
Approximation algorithms part three
(Fully) Polynomial Time Approximation Schemes
Benjamin Sach

Approximation Algorithms Recap
An algorithm A is an α-approximation algorithm for problem P if,
◦ A runs in polynomial time
◦ A always outputs a solution with value s
• Here P is an optimisation problem with optimal solution of value Opt
• If P is a maximisation problem,
Opt
α s Opt
within an α factor of Opt
• If P is a minimisation problem, Opt s α · Opt
We have seen:
a 3/2-approximation algorithm for Bin Packing
a 2-approximation algorithm for k-centers
a 3/2-approximation algorithm for scheduling multiple machines

The Subset Sum problem
4 4
7
322
t = 12

4 4
7
322
t = 12
• Let S be a multi-set of positive integers and t be a positive integer
|S| = m

4 4
7
322
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
|S| = m

4 4
7
322
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
Decision Problem Is there a subset, S ⊆ S with size t?
|S| = m

4 4
7
322
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
the size of S is a∈S a
|S| = m

t = 12
4
4
2
7
32
here S = {4, 2, 4, 7, 2, 3} and t = 12
|S| = m

t = 12
7
3
2
4 42
here S = {4, 2, 4, 7, 2, 3} and t = 12
|S| = m

4 4
7
322
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
Optimisation Problem
Find the size of the largest subset of S which is no larger than t
|S| = m

7
22
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
4
4
3
|S| = m

7
22
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
4
4
3
|S| = m
The answer to the
optimisation problem is ‘11’

4 4
7
322
t = 12
here S = {4, 2, 4, 7, 2, 3} and t = 12
The optimisation version is NP-hard
and the decision version is NP-complete
|S| = m

An exact solution
Let S = {s1, s2, s3 . . . sm} be the set of items and Si = {s1, s2, . . . , si}
4 4
7
322
S
S3
|S| = m

An exact solution
4 4
7
322
S
S3
Let Li be the set of sizes of all S ⊆ Si which are not larger than t
|S| = m

An exact solution
4 4
7
322
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
The largest subset of S (of size at most t) is the largest number in Lm
2
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
We compute Li from Li−1:
2
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
We compute Li from Li−1: Li = Li−1 ∪ (Li−1 + si)
2
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
where (x + si) ∈ (Li−1 + si) iff x ∈ Li−1 and x + si t
2
4 4
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
7
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
7
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
4
7
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
4
7
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
7
4 4
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
7
4 4
L3 + s4 = L3 + 7 =
{7, 9, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
4 4
7
2
L3 + s4 = L3 + 7 =
{7, 9, 11}
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
(here t = 12)
|S| = m
s4

An exact solution
S
S3
L3 =
{0, 2, 4, 6, 8, 10}
2
4 4
7
2
L3 + s4 = L3 + 7 =
{7, 9, 11}
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
(here t = 12)
We don’t have any duplicates in Li - so |Li| t
|S| = m
s4

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
◦ Compute (Li−1 + si) from Li−1
◦ Compute Li = Li−1 ∪ (Li−1 + si)
◦ Output the largest number in Lm
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
Each Li is of length |Li| t
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
The overall time complexity is therefore O(mt)
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
Is this polynomial in n?
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
n is the length of the input (measured in words)
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
a w bit word
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
a w bit word (conventionally w ∈ Θ(log n))
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
The input to the Subset Sum problem is a list of the elements of S along with t
encoded in binary in a total of n words
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
s1 s2 s3 t
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
s1 s2 s3 t
As m n, the time is O(nt)
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
s1 s2 s3 t
As m n, the time is O(nt) . . . but t could be (for example) 2n
|S| = m

An exact solution
The algorithm
◦ Let L0 = {0}
◦ For i = 1 . . . m:
O(1) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
What even is n?
Input
n words
s1 s2 s3 t
As m n, the time is O(nt) . . . but t could be (for example) 2n
|S| = m
. . . in other words O(n2n) time!

Pseudo-polynomial time algorithms
We say that an algorithm is pseudo-polynomial time
if it runs in polynomial time when all the numbers are integers nc
for some constant c

for some constant c
The algorithm for Subset Sum given takes O(nt) = O(nc+1) time
(in this case)

for some constant c
(in this case)
So there is a pseudo-polynomial time algorithm for Subset Sum

for some constant c
(in this case)
A diversion into computational complexity

for some constant c
(in this case)
We say that an NP-complete problem is weakly NP-complete if
there is a pseudo-polynomial time algorithm for it

for some constant c
(in this case)
The decision version of Subset Sum is weakly NP-complete

for some constant c
(in this case)
We say that an NP-complete problem is strongly NP-complete if
it remains NP-complete when all the numbers are integers nc

for some constant c
(in this case)
The decision version of Bin packing is strongly NP-complete

for some constant c
(in this case)
(this only makes sense if you rephrase the problem)

for some constant c
(in this case)
item sizes are
integers in [nc]
4
bins have size
t ∈ [nc]
(this only makes sense if you rephrase the problem)

Polynomial time approximation schemes
A Polynomial Time Approximation Scheme (PTAS) for problem P
is a family of algorithms:
For any constant > 0 there is an algorithm in the family, A
such that A is a (1 + )-approximation algorithm for P

• If we had a PTAS for Subset Sum we could:

Let = 0.1 so that A0.1 runs in polynomial time and
outputs a subset of size at least
Opt
1.1 > 0.9 · Opt

Let = 0.01 so that A0.01 also runs in polynomial time and
Opt
1.01 > 0.99 · Opt
Opt
1.1 > 0.9 · Opt

Opt
1.01 > 0.99 · Opt
Opt
1.1 > 0.9 · Opt
Opt
1.001 > 0.999 · Opt

Opt
1.1 > 0.9 · Opt
A PTAS does not have to have a time complexity which is polynomial in 1/

Opt
1.1 > 0.9 · Opt
A can have a time complexity of O(n
c
) for example

Opt
1.1 > 0.9 · Opt
A can have a time complexity of O(n
c
) for example
O(n10c) vs. O(n100c) vs. O(n1000c) in our example
= 0.1 = 0.01 = 0.001

Opt
1.1 > 0.9 · Opt
A fully PTAS (FPTAS) has a time complexity which is polynomial in 1/ (as well as polynomial in n)

Opt
1.1 > 0.9 · Opt
i.e. the time complexity is O((n/ )c) for some constant c

Opt
1.1 > 0.9 · Opt
In our example O((10n)c) = O((100n)c) = O((1000n)c) = O(nc)
= 0.1 = 0.01 = 0.001

A PTAS for Subset Sum
Recall that Li is the set of sizes of all S ⊆ Si which are not larger than t
(where Si = {s1, s2, . . . , si} - the ﬁrst i numbers in the input)
3
S
S4
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
2
4 2 24
7
(here t = 12)
4
2
4
7
4
4
7
2
4
4
2
7
4

The exact algorithm for Subset Sum was slow (in general) because
each list of possible subset sizes Li could become very large
3
S
S4
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
2
4 2 24
7
(here t = 12)
4
2
4
7
4
4
7
2
4
4
2
7
4

Key Idea Construct a trimmed version of Li (denoted Li ⊆ Li) so that

Li is a subset of Li (i.e. Li ⊆ Li)

The length of Li is polynomial in the input length (i.e. |Li| nc for some c)

For every y ∈ Li, there is a z ∈ Li which is almost as big

Consider this process called Trim. . . Trim(Li, δ): Include Li[j] in Li iff
where prev is the previous
Li[j] > (1 + δ) · prev
entry we included in Li

L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
2 4
2
4
7
4
4
7
2
4
4
2
7
4
Li[j] > (1 + δ) · prev

for δ = 1. . . L4 = {0, 2, 6}
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
2 4
2
4
7
4
4
7
2
4
4
2
7
4
Li[j] > (1 + δ) · prev

for δ = 1. . . L4 = {0, 2, 6}
L4 = {0, 2, 4, 6, 7, 8, 9, 10, 11}
2 4
2
4
7
4
4
7
2
4
4
2
7
4
Li[j] > (1 + δ) · prev
L4 is a small subset of L4 and for any y ∈ L4,
there is an z ∈ L4 with z y/2

Li[j] > (1 + δ) · prev
Unfortunately, this hasn’t really achieved anything. . .

Li[j] > (1 + δ) · prev
we don’t have time to compute Li and then trim it
(because Li might be very big)

Li[j] > (1 + δ) · prev
we don’t have time to compute Li and then trim it
Instead, we will trim as we go along. . .
(because Li might be very big)

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
◦ Compute U = Li−1 ∪ (Li−1 + si)
◦ Let Li = Trim(U, δ)
- Li is the trimmed version of Li
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
Trim(U, δ): Include U[j] in Li iff U[j] > (1 + δ) · prev
where prev is the previous thing we included in Li
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
2
2
4
Li−1 = si = 3
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
2
2
4
Li−1 = si = 3
2
(Li−1 + si) =
3
3
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
2
2
4
Li−1 = si = 3
2
(Li−1 + si) =
U = Li−1 ∪ (Li−1 + si) =
2
2
42
3 4
3
3
3
2
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
2
2
4
Li−1 = si = 3
2
(Li−1 + si) =
U = Li−1 ∪ (Li−1 + si) =
2
2
42
3
= Li = Trim(U, δ)
2
(with δ = 1)
4
3
3
3
2
2
3
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
2
2
4
Li−1 = si = 3
2
(Li−1 + si) =
U = Li−1 ∪ (Li−1 + si) =
2
2
42
3
= Li = Trim(U, δ)
2
(with δ = 1)
4
3
3
3
keep each thing if it is more than (1 + δ)
times as big as the last thing you kept
2
2
3
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
O(|Li|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
O(|Li|) time
O(|Lm|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
O(|Li|) time
This algorithm throws away some possible subsets,
O(|Lm|) time
but it always outputs a valid subset (but probably not the largest one)
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
O(|Li|) time
Two questions remain. . .
O(|Lm|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li−1|) time
O(|Li|) time
Two questions remain. . .
O(|Lm|) time
How big is |Li|? How good is the solution given?
|S| = m

Li vs. Li
Lemma For any y ∈ Li there is an z ∈ Li with
y
(1+δ)i z y
|S| = m

Li vs. Li
y
(1+δ)i z y
For any entry in the original set (Li) . . .
there is one in the trimmed set (Li) . . .
of a ‘similar’ size (δ is very small)
|S| = m

Li vs. Li
y
(1+δ)i z y
Proof (by induction)
|S| = m

Li vs. Li
y
(1+δ)i z y
Base Case: L0 = L0 = {0}
|S| = m

Li vs. Li
y
(1+δ)i z y
Inductive step: Assume that the lemma holds for (i − 1)
|S| = m

Li vs. Li
y
(1+δ)i z y
As y ∈ Li we have that either y ∈ Li−1 or (y − si) ∈ Li−1
|S| = m

Li vs. Li
y
(1+δ)i z y
if y ∈ Li−1 then there is a x ∈ Li−1 with
y
(1+δ)(i−1) x y
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
by the inductive hypothesis
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
By the deﬁnition of Trim there is some z ∈ Li with z x z · (1 + δ)
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
So we have that z x y and z x
1+δ
y
(1+δ)i
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
1+δ
y
(1+δ)i
I.e. that there is an z ∈ Li with
y
(1+δ)i z y as required
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
1+δ
y
(1+δ)i
The case that (y − si) ∈ Li−1 is almost identical
y
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1+δ)(i−1) x y
1+δ
y
(1+δ)i
The case that (y − si) ∈ Li−1 is almost identical (we omit it for brevity)
y
|S| = m

Li vs. Li
y
(1+δ)i z y
By setting i = m and δ = /2m we have that,
For any y ∈ Lm there is a z ∈ Lm with
y
(1 + 2m )m
z y
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1 + 2m )m
z y
Further, Opt ∈ Lm meaning there is a z ∈ Lm with
Opt
1 + 2m
m z Opt
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1 + 2m )m
z y
Opt
1 + 2m
m z Opt
Recall that the output of the algorithm is the largest number in Lm. . .
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1 + 2m )m
z y
Opt
1 + 2m
m z Opt
We only need to show that 1 + 2m
m
1 + . . .
|S| = m

Li vs. Li
y
(1+δ)i z y
y
(1 + 2m )m
z y
Opt
1 + 2m
m z Opt
We only need to show that 1 + 2m
m
1 + . . .
|S| = m
VS
Opt
1 +
z Opt

Li vs. Li
We need to show that 1 + 2m
m
1 + (for 0 < 1)
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
ex
= ∞
i=0
xi
i!
1 + x + x2
This follows from the following facts:
ex (1 + x
m )m for all x, m > 0
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
So the output of the algorithm is some z where,
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
Opt
1 +
Opt
1 + 2m
m z Opt
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
Opt
1 +
z Opt
|S| = m

Li vs. Li
m
1 + (for 0 < 1)
1 +
2m
m
e /2
1+
2
+
2
2
1+
But how long does it take to run?
Opt
1 +
z Opt
|S| = m

How big is Li?
The time complexity depends on |Li|. . .
|S| = m

How big is Li?
By the deﬁnition of Trim we have that,
any two successive elements, z, z of Li have
z
z 1 + δ = 1 + 2m
|S| = m

How big is Li?
z
z 1 + δ = 1 + 2m
Further, all elements are no greater than t
|S| = m

How big is Li?
z
z 1 + δ = 1 + 2m
So Li contains at most O(log(1+δ) t) elements
|S| = m

How big is Li?
z
z 1 + δ = 1 + 2m
log(1+δ) t =
ln t
ln(1 + ( /2m))
2m(1 + ( /2m)) ln t
= O
m log t
|S| = m

How big is Li?
z
z 1 + δ = 1 + 2m
log(1+δ) t =
ln t
ln(1 + ( /2m))
2m(1 + ( /2m)) ln t
= O
m log t
ln(1 + x) > x
x+1
(here x = /2m)
another fact:
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li|) time
O(|Li|) time
O(|Lm|) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li|) time
O(|Li|) time
As |Li| = O(m log t/ ), the algorithm runs in
O(|Lm|) time
O(m2 log t/ ) = O(n3 log n/ ) time
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li|) time
O(|Li|) time
O(|Lm|) time
|S| = m
m n
log t = O(n log n)
Recall that n is the length of the input (measured in words)

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li|) time
O(|Li|) time
The output z is such that
O(|Lm|) time
Opt
1 +
z Opt
|S| = m

The algorithm
◦ Let L0 = {0}, δ = /(2m)
◦ For i = 1 . . . m:
O(|Li−1|) time
O(|Li|) time
O(|Li|) time
O(|Lm|) time
Opt
1 +
z Opt
So this is in fact an FPTAS for Subset Sum
|S| = m

A Polynomial Time Approximation Scheme (PTAS) for problem P is a family of algorithms:
We have seen an FPTAS for Subset Sum
e.g. the time complexity could be O(n
c
) (for example)
which runs in O(n3 log n/ ) time
Opt
1 +
z Opt

Approximation Algorithms Part Three: (F)PTAS

Recommended

More Related Content

What's hot (18)

Similar to Approximation Algorithms Part Three: (F)PTAS (20)

More from Benjamin Sach (20)

Recently uploaded (20)

Approximation Algorithms Part Three: (F)PTAS