O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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
and task T
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 first, 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 defines 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 finite 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 finding
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 define 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 define 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.

Start Free Trial

No credit card required