Algorithms Chapter 27 Algorithms Sequential Parallel And Distributed Approximation Algorithms Glance Table Contents Overview

Algorithms: Sequential, Parallel and Distributed 1-1

Chapter 27

Approximation Algorithms

At a Glance

Table of Contents

• Overview

• Objectives

• Instructor Notes

• Solutions to Selected Exercises

Algorithms: Sequential, Parallel and Distributed 1-2

Lecture Notes

Overview

In Chapter 27 we discuss the problem of finding efficient approximation algorithms for those

problems that are NP-hard. We define the notion of a k-approximation, and design k–

approximations for the Euclidean version of the traveling salesman problem, for the bin

packing problem, for the Steiner tree problem, and for the facility location problem.

Chapter Objectives

After completing the chapter the student will know:

• The definition a k-approximation to an optimization decision problem

• An O(n2) algorithm for a 2-approximation for the Euclidean version of the traveling

salesman problem, but that for any k, an algorithm giving a k-approximation for the general

traveling salesman problem would imply that P = NP

Instructor Notes

In Exercise 27.13 the graph shown was missing a weight on edge {3,8}. In doing the

exercise, we placed a weight of 6 on this edge for definiteness.

The discussion on p. 848 establishing the approximation result shown in formula (27.2.5) can

be improved. It would best proceed by first establishing the following two lemmas. The sets

A,B,C,D discussed are those defined on p. 848. The proof of the Lemma 1 follows the exact

same lines that that given for case 1 on p. 848.

Lemma 1. Suppose all but at most one of the m bins in a bin packing are at least 2/3 full.

Then m ≤ m* + 1.

Proof. If si denotes the amount in bin i, we have:

m

1

m

Lemma 2. Suppose in the first-fit decreasing bin packing that there is a bin that only contains

objects from the set D. Then all but at most one of the m bins in a bin packing are at least 2/3

full.

Solutions to Selected Exercises

Section 27.1 The Traveling Salesman Problem

27.2 Of course it is required that n ≥ 4. We give an example for K4. It is straightforward to

generalize to Kn for an arbitrary n > 4. In the figure below, growing a minimum

27.3 Let G = (V,E) be any instance of the Hamiltonian cycle decision problem. Consider the

instance of TSP on the complete graph G = (V,E) with the following weighting: (u,v) = 1 if

uv  E, otherwise (u,v) =  |V | + 1. Note that a Hamiltonian cycle in G would have cost |V |,

Algorithms: Sequential, Parallel and Distributed 1-5

Section 27.2 Bin Packing

27.6 Let si denote the sum of the sizes of all of the objects placed in bin i, 1 ≤ i ≤ m*. Then

0 < si ≤ 1 and

*1

*

1

*

1mFs m

i

m

ii===  ==

. But since m* is an integer, it follows that

27.7 a. Next fit uses 5 bins Bi, with the placement:

27.8 a. First fit uses 5 bins Bi, with the placement:

27.9 a. First fit decreasing uses 4 bins Bi, with the placement:

B1: .9, .1 B2: .7, .15, .1 B3: .6, .4 B4: .4, .35

.

27.11 Using the two lemmas discussed in the Instructor Notes above, we can assume that no

bin contains only objects from set D. Note that in this case, using the first-fit decreasing

packing the number of bins would remain the same if the set D is empty. Thus, we can assume

that our objects only consist of objects from A, B, and C. In the latter case, the first-fit

Algorithms: Sequential, Parallel and Distributed 1-7

Section 27.3 The Steiner Tree Problem

27.13 Note: There was a missing weight on edge {3,8}, which we took to be 6 in the figure

Algorithms: Sequential, Parallel and Distributed 1-8

Section 27.4 The Facility Location Problem

27.16

27.17 We show Vertex Cover  Dominating Set. Let G be any graph, and suppose we ask

whether G has a vertex cover C of size k.. Construct a graph G as follows. The vertex set of

G will consist of all vertices of G, except isolated vertices. For each edge {a,b} in G, we also

add a vertex v{a,b} to G. The edge set of G will be a bunch of triangles consisting of all edges

27.18 We show that the Dominating Set  ρ-approximation to the facility location with ρ < 2.

Let G be a graph and we ask whether G has a domination set of size ≤ k. Construct a

complete graph G from G by adding all edges not in G. Then define a weighting on G by

27.19 First note that VertexCoverApprox actually produces a vertex cover, since an edge is

only deleted when it is adjacent to a vertex that has already been covered by an edge in the