On two segmentation problems

The hypercube segmentation problem is the following: Given a set S of m vertices of the discrete d-dimensional cube {0, 1}(d), and k vertices P1,...,Pk, P-i is an element of {0, 1}(d) and a partitions of S into k segments S,,...,S, so as to maximize the sum Sigma(i=1)(k) Sigma(c is an element of Si) P-i.c, where . is the overlap operator between two vertices of the d-dimensional cube, defined to be the number of positions they have in common. This problem (among other ones) was considered by Kleinberg, Papadimitriou, and Raghavan, where the authors designed a deterministic approximation algorithm that runs in polynomial time for every fixed k and produces a solution whose value is within 0.828 of the optimum, as well as a randomized algorithm that runs in linear time for every fixed k and produces a solution whose expected value is within 0.7 of the optimum. Here we design an improved approximation algorithm; for every fixed is an element of > 0 and every fixed k our algorithm produces in linear time a solution whose value is within (1 - is an element of) Of the optimum. Therefore, for every fixed k, this is a polynomial approximation scheme for the problem. The algorithm is deterministic. but it is convenient to first describe it as a randomized algorithm and then to derandomize it using some properties of expander graphs. We also consider a segmented version of the minimum spanning tree problem, where we show that no approximation can be achieved in polynomial time, unless P = NP. (C) 1999 Academic Press.