## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required Chapter 9
Exercises going beyond
NP-completeness
This chapter presents a set of exercises related to Chapter 8. The main focus
is on approximation results (Section 9.1), and there are also exercises deal-
ing with linear programming, randomized algorithms, and branch-and-bound
techniques (Section 9.2). Solutions are provided in Section 9.3.
9.1 Approximation results
Exercise 9.1: Single machine scheduling (solution p. 219)
We have n independent tasks, T
1
, . . . , T
n
, to execute on a single computer. For
any 1 j n, the execution time of task T
j
is w
j
j
is submitted
to the system at time r
j
. In other words, the processing of task T
j
cannot
start earlier than time r
j
. We denote by C
j
the completion time of t ask T
j
,
that is, the time at which its processing completes. We assume th at w
j
is a
positive integer and r
j
is a nonnegative integer.
The objective function is the sum of the completion times: S =
n
j=1
C
j
.
1. We assume in this question that tasks can be preempted (we explain
below in detail what preemption is). P rove that in this framework the
optimal solution is obtained by scheduling during each interval [i; i + 1],
for any nonnegative integer i, the task whose remaining processing time
is the smallest. This scheduling algor ithm is called Shortest Remaining
Processing Time ﬁrst, or SRPT.
To explain preemption, let us consider a task T
j
that is executed
during the time interval [i; i + 1] (where i is some integer) and whose
processing has not completed at time i + 1. We allow another task T
k
(with j = k) to be processed during the time interval [i + 1; i + 2].
The execution of task T
j
will eventually be resumed. The sum of the
durations of the time intervals d uri ng which T
j
is executed is equal to
w
j
; when the execution of T
j
resumes after a preemption, it restarts
from where it was interrupted.
211
© 2014 by Taylor & Francis Group, LLC 212 Chapter 9. Exercises going beyond NP-completeness
2. We order the tasks by their completion times under an execution of
algorithm SRPT using preemption. Prove that scheduling the tasks
according to this order deﬁnes an approximation algorithm for the case
without preemption. (We admit that the problem is NP-hard.)
Exercise 9.2: SUBSET-SUM
(solution p. 221)
In Exercise 7.19 (p. 155), we proved that the decision problem SUBSET-SUM
was NP-complete. Here we focus on the associated optimization problem:
Given a ﬁnite set S of positive integers, and an integer t, we look for a sub set
S
of S such that the sum of its elements is the largest possible while being
not greater than t (
xS
x t). We call the sum of the elements of S
the
optimal sum.
Let S = {x
1
, x
2
, . . . , x
n
}. In the following, we assume that all the lists are
sorted in nondecreasing order. Given a list of integers L and an integer x,
L + x denotes the list of integers obtained by adding x to each of the elements
of L. Given two (sorted) lists L and L
, we denote by Merge(L, L
) the sorted
union of the elements of the two lists. Algorithm 9.1 is an attempt at ﬁnding
the optimal sum.
1 n |S|
2 L
0
{0}
3 for i = 1 to n do
4 L
i
Merge(L
i1
, L
i1
+ x
i
)
5 Discard from L
i
any element greater than t
6 return the largest element of L
n
ALGORITHM 9.1: Sum(S, t).
1. Does Algorithm 9.1 return the optimal sum?
2. What is the complexity of Algorithm 9.1?
In order to deﬁne an approximation algorithm for the SUBSET-SUM prob-
lem, we introduce Algorithm 9.2, which takes as input a sorted list and a
threshold δ and outputs a subset of the original list such that two consecutive
elements are at least at a factor 1 + δ from each other. We use this algorithm
to deﬁne Algorithm 9.3.
3. Evaluate the number of elements in L
i
at the end of Step 6. What is
the complexity of Algorithm 9.3?
4. Show that Algorithm 9.3 is a fully polynomial-time approximation scheme
(FPTAS).
© 2014 by Taylor & Francis Group, LLC

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required