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

Problem Set 2

1. In the longest substring problem, we are given a set of strings S = {s_{1}, …, s_{n}} and are asked to determine the longest string s that is a substring of all of the n strings. Is the longest substring problem solvable in polynomial time? Provide an answer by either giving a polynomial-time algorithm or proving that the problem is NP-complete.

2. Exercise 2.9.

3. Consider the following optimization problem called rectangle covering.

• Instance: A collection of rectangles I = {R_{1}, …, R_{n}} in the plane such that each rectangle is aligned with the axes; that is, all sides are horizontal or vertical. Note that the rectangles may overlap.

• Solution: A collection of points P = {p_{1}, …, p_{m}} in the plane such that each rectangle in I contains at least one point from P.

• Goal: Minimize |P |.

Provide the best approximation algorithm you can for the rectangle covering problem. Analyze the approximation ratio and the running time of your algorithm.

4. Exercise 7.1.

5. Exercise 6.2.