Tel-Aviv University - Computer Science Colloquium
Sunday, April 18, 14:15-15:15
at 14:00 The hypercube segmentation problem is the following: Given a set S of m vertices of the discrete d-dimensional cube {0,1}^d, find k vertices P_1, ... , P_k, P_i in {0,1}^d and a partitions of S into k segments S_1, ..., S_k so as to maximize the sum \sum_{i=1}^k \sum_{c \in S_i} P_i \odot c, where \odot 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) is considered in a recent paper by Kleinberg, Papadimitriou and Raghavan, where the authors design 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 \epsilon >0 and every fixed k, our algorithm produces in linear time a solution whose value is within (1-\epsilon) 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.
Joint work with Noga Alon.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html