College of Computer & Information Science Spring 2004 Northeastern University Handout 5 CSG399: Approximation Algorithms 25 February 2003

Problem Set 3 (discussion day: March 8)

1. PARTITION

Consider the following optimization version of the Partition problem. Given a set X = {x_{1}, x_{2}, …, x_{n}} of n integers, find a partition of X into two subsets X_{1} and X_{2} that minimizes the quantity:

max{ ∑_{x∈X_{1}} x, ∑_{x∈X_{2}} x}.

In this exercise, we derive a PTAS for the Partition problem using the enumeration technique we used to dervive PTASs for knapsack and bin-packing.

Consider the following heuristic for some fixed integer k: (i) Choose the k largest x_{i}’s. (ii) Find the optimal partition of these k integers using some exhaustive method. (iii) Complete this into a partition of X by considering each of the remaining x_{i}’s in turn and adding it to the partition which at the time has the smallest sum.

(a) (3 points) Show how to implement the above heuristic in time O(2^{k} + n).

(b) (12 points) Prove that the above heuristic achieves an approximation ratio of 1 + \frac{1}{2+k}.

(c) (5 points) Using the claims of parts (a) and (b), choose k appropriately such that the above heuristic yields a PTAS for Partition.

2. An independent set of an undirected graph G is a subset V′ of vertices such that no two vertices in V′ have an edge in G. The IndependentSet problem is to find a maximum-size independent set in G. It is known that IndependentSet is NP-complete. In this problem, we investigate the approximability of IndependentSet.

Define the product of two graphs G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) as G = (V, E), where

V = {⟨v_{1}, v_{2}⟩ : v_{1} ∈ V_{1}, v_{2} ∈ V_{2}},

and there is an edge between vertices ⟨u_{1}, u_{2}⟩ and ⟨v_{1}, v_{2}⟩ in G if either u_{1} = v_{1} and (u_{2}, v_{2}) ∈ E_{2} or (u_{1}, v_{1}) ∈ E_{1}. For a positive integer n, let G^{n} be defined by the recurrence relation G^{i+1} = G^{i} × G and G^{1} = G.

(a) (5 points) Prove that G has an independent set of size k if and only if G^{n} has an independent set of size k^{n}.

(b) (5 points) Give a polynomial-time algorithm to construct an independent set of G of size ⌈k^{1/n}⌉ from any independent set of G^{n} of size k.

(c) (10 points) Using parts (a) and (b), argue that if there exists a constant c such that there is a polynomial-time c-approximation algorithm for IndependentSet, then there exists a PTAS for IndependentSet.

3. The bottleneck TSP problem is the problem of finding a Hamiltonian cycle in a given weighted undirected graph such that the length of the longest edge in the cycle is minimized. Assuming that the input graph satisfies the triangle inequality, show that this problem has a polynomial-time approximation algorithm with ratio 3.

4. Exercise 3.10.

5. Exercise 11.3.