A note on “Approximation schemes for a subclass of subset selection
problems”, and a faster FPTAS for the Minimum Knapsack Problem
Cédric Bentza , Pierre Le Bodicb,∗
a CEDRIC-CNAM,

arXiv:1607.07950v1 [cs.CC] 27 Jul 2016

b Faculty

292 rue Saint-Martin, 75141 Paris Cedex, France
of Information Technology, Monash University, Australia

Abstract
Pruhs and Woeginger [10] prove the existence of FPTAS’s for a general class of minimization and maximization subset selection problems. Without losing generality from the original framework, we prove how
better asymptotic worst-case running times can be achieved if a ρ-approximation algorithm is available, and
in particular we obtain matching running times between maximization and minimization subset selection
problems. We directly apply this result to the Minimum Knapsack Problem, for which the original framework yields an FPTAS with running time O(n5 /ǫ), where ǫ is the required accuracy and n is the number of
items, and obtain an FPTAS with running time O(n3 /ǫ), thus improving the running time by a quadratic
factor in the worst case.
Keywords: Approximation algorithm, Approximation scheme, FPTAS, Worst case analysis,
Pseudo-polynomial algorithm, Combinatorial optimization, Minimum Knapsack Problem

1. Introduction
Pruhs and Woeginger [10] give a simple and elegant proof of the existence of an FPTAS for a set of
general subset selection problems, provided there exists an exact algorithm that runs in pseudo-polynomial
time. We recall the main definition and result.
Definition 1 ([10]). A subset selection problem P is a combinatorial optimization problem whose instances
I = (X, w, S) consist of:
• a ground set X with |X| = n elements;
• a positive integer weight w(x) for every x ∈ X;
• a structure S that is described by ℓ(S) bits.
The structure S controls which subset of elements of X is feasible or infeasible, and its encoding length
ℓ(S) is used when analyzing the running time of an algorithm. As in [3, Chapter 1], we assume that ℓ(S)
reflects the encoding length of the structure S in a “reasonable encoding scheme” of I. An example is given
in Section 4. The sumP
of the weights of an instance I = (X, w, S) will be referred to as the “total weight”
and is equal to W := x∈X w(x). In all the problems that will be considered in this note, one looks for a
solution, i.e., one wishes to select a subset X ′ ⊆ X, which
is feasible (i.e., respects some constraint given by
P
S) and either maximizes or minimizes the quantity x∈X ′ w(x).
Examples of such problems include the Maximum Independent Set Problem (a maximization problem
where elements are vertices of a graph, and the structure S ensures that only non-adjacent elements can be
∗ Corresponding

author
Email addresses: cedric.bentz@cnam.fr (Cédric Bentz), pierre.lebodic@monash.edu (Pierre Le Bodic)

Preprint submitted to Elsevier

July 28, 2016

selected), and the Maximum Knapsack Problem (a maximization problem over a set of items, the elements,
where the structure S contains a single packing constraint). Note that, among these problems, some are
strongly NP-hard (like the former one [3]), while others are weakly NP-hard (like the latter one [3]).
Throughout the paper, we use polynomials of the form p(n, M, ℓ(S)) to bound asymptotic running times
of algorithms, where M is a value that depends on n and/or W , and can for instance be equal to W . Since
the first and the third arguments are invariably n and ℓ(S), respectively, we will simply use the notation
p(M ) (where M is substituted for the ad hoc value) wherever clarity is unimpaired.
Theorem 1 ([10]). Let P be a subset selection problem with instances I = (X, w, S) that satisfies the
following condition:
(C) There exists an algorithm A that solves P to optimality and whose running time is bounded by a
polynomial p in n, in total weight W , and in ℓ(S).
Then problem P has an FPTAS with running time n · p(n3 /ǫ) for minimization and n · p(n) + p(n2 /ǫ) for
maximization.
We refer to [10] for all other definitions, notation and references.
In their paper, Pruhs and Woeginger point out that many existing proofs for the existence of FPTAS’s
for subset selection problems require a “separate argument” to provide a lower or upper bound (respectively,
for minimization or maximization problems) on the optimal value, and they provide a graceful proof that
does not use bounds. However, the resulting FPTAS may have a higher asymptotic running time that one
that uses a lower or upper bound. The contribution of this note is Theorem 2.
Theorem 2. Let P be a subset selection problem with instances I = (X, w, S) that satisfies (C). Suppose
w.l.o.g. that the following condition holds:
(C ′ ) There exists a ρ-approximation algorithm A′ to problem P whose running time is bounded by a polynomial p′ in n, in M = log(W ), and in ℓ(S).
Then problem P has an FPTAS with running time p′ (log(W )) + p(n2 /ǫ) (for both minimization and
maximization), if ρ is a constant.
In Theorem 2, we can suppose without loss of generality that a ρ-approximation algorithm A′ exists,
since P satisfies (C), and thus there exists an FPTAS by Theorem 1. The proof of Theorem 2 is given
in Section 2, and the running time analysis in Section 3. Although it is possible to use A with a given ǫ
instead of algorithm A′ in Theorem 2, doing so may not provide running time improvements. However, we
will prove in Section 4 that Theorem 2 provides an FPTAS with a faster running time than Theorem 1 on
an important example, the Minimum Knapsack Problem.
2. Proof of Theorem 2
The proof follows the one given by Pruhs and Woeginger in [10], with some simplifications due to
assumption (C ′ ). To begin with, we will not need to suppose that items are ordered by non-decreasing
weights.
2.1. Proof for minimization problems
Assumption (C ′ ) implies that, for a given ρ > 1, and for any instance I,
OP T ≤ U B ≤ ρ · OP T,

(1)

where OP T is the optimal value of instance I and U B is the upper bound returned by A′ on I.
We define the scaling parameter
Z :=

ǫ 1
· · U B.
ρ n
2

(2)

We create a modified instance I ′ where only weights differ from I. Let w′ be the weights of I ′ such that,
for i = 1, . . . , n,
(
⌈w(xi )/Z⌉
if w(xi ) ≤ U B,
′
w (xi ) =
(3)
U B/Z + n + 1 otherwise.
The total weight W ′ of instance I ′ is thus bounded by
W ′ ≤ n · (U B/Z + n + 1) ≤ n · (ρ · n/ǫ + n + 1).

(4)

Since ρ is fixed, instance I ′ can be solved in a time polynomial in the size of instance I and in 1/ǫ by A. Let
Y ∗ denote an optimal solution (of value OP T ) for instance I, and Y ′ for instance I ′ . Observe that, because
OP T ≤ U B, any item i in Y ∗ satisfies w(xi ) ≤ U B. Since Y ′ is an optimal solution of I ′ , and Y ∗ is feasible
for I ′ (since the structure S is the same in I and in I ′ ), we have:
X
X
{w′ (y)|y ∈ Y ′ } ≤
{w′ (y)|y ∈ Y ∗ }
(5a)
X
≤
{⌈w(y)/Z⌉|y ∈ Y ∗ }
(5b)
X
{w(y)/Z + 1|y ∈ Y ∗ }
(5c)
≤
≤ OP T /Z + n
≤ U B/Z + n.

(5d)
(5e)

Equations (5e) and (3) imply that, if there exists i ∈ {1, . . . , n} such that w(xi ) > U B, xi cannot belong to
an optimal solution Y ′ to I ′ . We are now ready to prove that Y ′ is a (1 + ǫ)-approximate solution to I.
X
X
{w(y)|y ∈ Y ′ } ≤ Z ·
{w′ (y)|y ∈ Y ′ }
by (3)
(6a)
≤ OP T + n · Z
ǫ 1
= OP T + n · · · U B
ρ n
≤ (1 + ǫ) · OP T

by (5d)

(6b)

by (2)

(6c)

by (1).

(6d)

2.2. Proof for maximization problems
For maximization problems, assumption (C ′ ) implies that, for a given ρ < 1,
OP T ≥ LB ≥ ρ · OP T,

(7)

where LB is the value returned by A′ .
We define the scaling parameter Z as
Z := ǫ ·

1
· LB.
n

(8)

We create a modified instance I ′ where only weights differ from I. We use the property that, if w(xi ) > LB/ρ
for some i ∈ {1, . . . , n}, then item xi cannot belong to a feasible solution to I (and hence to I ′ ), because of
(7). Therefore, we encode the weights w′ of I ′ as
(
⌊w(xi )/Z⌋ if w(xi ) ≤ LB/ρ,
w′ (xi ) =
(9)
1
otherwise.

3

The total weight W ′ of instance I ′ is thus bounded by
W′ ≤


j−1 
X
n · w(xi )

ǫ · LB


n
≤n
+ n.
ǫ·ρ
i=1

+

n
X

1 (for some j ≥ 2)

by (8)

i=j

(10)

Since ρ is fixed, instance I ′ can be solved in a time polynomial in the size of instance I and in 1/ǫ by A.
We use again notation Y ∗ and Y ′ . Because Y ∗ is feasible for I ′ (since the structure S is the same in I and
in I ′ ), we have
X
X
{w′ (y)|y ∈ Y ′ } ≥
{w′ (y)|y ∈ Y ∗ }.
(11)
We now prove that Y ′ is a (1 − ǫ)-approximate solution to I.
X
X
{w(y)|y ∈ Y ′ } ≥ Z ·
{w′ (y)|y ∈ Y ′ }
X
≥Z·
{w′ (y)|y ∈ Y ∗ }
X
{⌊w(y)/Z⌋|y ∈ Y ∗ }
=Z·
X
{w(y)/Z − 1|y ∈ Y ∗ }
≥Z·
X
{w(y)|y ∈ Y ∗ } − |Y ∗ | · Z
≥
≥ OP T − n · ǫ ·

1
· LB
n

≥ (1 − ǫ)OP T

by (9)
by (11)
by (9)

by (8)
by (7).

3. Running time comparisons
The following table gives the asymptotic worst-case running times if one only uses A, as in [10], or both
A and A′ , as in this paper.
A
A & A′

Minimization
n · p(n3 /ǫ)
′
p (log(W )) + p(n2 /ǫ)

Maximization
n · p(n) + p(n2 /ǫ)
p′ (log(W )) + p(n2 /ǫ)

The FPTAS for minimization problems that uses A (see [10]) first sorts the items in O(n log n) time,
constructs auxiliary instances in O(n2 ) time, and solves all instances in O(n · p(n3 /ǫ)) time. The FPTAS
for maximization problems that uses A (see [10]) first sorts the items in O(n log n) time, solves an instance
for each item in O(n · p(n)) time, constructs an auxiliary instance in O(n) time, and solves it in O(p(n2 /ǫ))
time. The FPTAS for minimization or maximization problems that uses A and A′ builds an approximate
solution in p′ (log(W )) time, constructs instance I ′ in O(n) time, and solves it in O(p(n2 /ǫ)) time (since
W ′ = O(n2 /ǫ) if ρ is fixed, from (4) and (10)). In Section 4, we show in particular how a quadratic
improvement on the running time can be achieved on the Minimum Knapsack Problem using both A and
A′ .
4. Application of Theorem 2 to the Minimum Knapsack Problem
The Minimum Knapsack Problem (MinKP) [8, Chapter 13] has been studied less extensively than its
maximization counterpart, MaxKP. Basically, MinKP is a minimization problem over a set of items (the
elements) where the structure S contains a single covering constraint. Constant-ratio approximation algorithms for this problem are given in [1, 2, 6], but, excluding [10], there does not seem to be any explicit
4

description and/or analysis of an FPTAS for it in any reference books or articles. The classical papers by
Ibarra and Kim [7] and Lawler [9] only deal with MaxKP, and the results in these papers do not seem to be
directly applicable to MinKP. Gens and Levner [4, 5] state that FPTAS’s for MinKP exist, based in part on
a paper by Sahni [11], but do not give proofs and only partial analyses. The idea that the result of Pruhs
and Woeginger [10] could be improved stemmed from Gens and Levner’s papers.
We show how directly applying Theorem 2 to the Minimum Knapsack Problem yields a quadratic improvement over Theorem 1. Note that the FPTAS’s these two theorems provide have the same asymptotic
running time for the Maximum Knapsack Problem.
The structure S that encodes (in)feasibility corresponds to the coefficients of the knapsack constraint,
together with the right hand side of the constraint. Its encoding length ℓ(S) hence corresponds to the sum
of the binary encodings of each of these numbers.
The dynamic programming algorithm in e.g. [12, Chapter 8] runs in p(n, W, ℓ(S)) = n · W , and may
be used as algorithm A. (Note that, for exact resolution, minimum and maximum knapsack problems
are equivalent, and hence both are weakly NP-hard [3].) Using only algorithm A, Theorem 1 ensures the
existence of an FPTAS that runs in O(n5 /ǫ). The 2-approximation given in [2] runs in a time bounded by
p′ (n, M = log(W ), ℓ(S)) = n2 and may serve as algorithm A′ . Using both A and A′ , Theorem 2 guarantees
the existence of an FPTAS with running time O(n3 /ǫ), which is a quadratic improvement over the FPTAS
provided by Theorem 1.
Acknowledgements
The authors would like to thank Ulrich Pferschy for introducing them to the original paper [10].
References
References
[1] T. Carnes and D. Shmoys. Primal-Dual Schema for Capacitated Covering Problems, pages 288–302. Springer Berlin
Heidelberg, Berlin, Heidelberg, 2008.
[2] J. Csirik, J. B. G. Frenk, M. Labbé, and S. Zhang. Heuristics for the 0-1 min-knapsack problem. Acta Cybern., 10(12):15–20, September 1991.
[3] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman &
Co., 1979.
[4] G. Gens and E. Levner. Computational complexity of approximation algorithms for combinatorial problems. In Jirı́
Becvár, editor, MFCS, volume 74 of Lecture Notes in Computer Science, pages 292–300. Springer, 1979.
[5] G. Gens and E. Levner. Complexity of approximation algorithms for combinatorial problems: a survey. SIGACT News,
12(3):52–65, 1980.
[6] M. Güntzer and D. Jungnickel. Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem.
Operations Research Letters, 26(2):55–66, 2000.
[7] O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM,
22(4):463–468, October 1975.
[8] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer, 2004.
[9] E. L. Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4(4):339–356,
1979.
[10] K. Pruhs and G. J. Woeginger. Approximation schemes for a class of subset selection problems. Theoretical Computer
Science, 382(2):151 – 156, 2007.
[11] S. Sahni. Approximate algorithms for the 0/1 knapsack problem. J. ACM, 22(1):115–124, January 1975.
[12] V. V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., 2001.

5

