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 ﬁ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 (

x∈S

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

i−1

, L

i−1

+ 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

Start Free Trial

No credit card required