### Abstract

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} ∈ {0, 1}^{d} and a partitions of S into k segments S_{1},..., S_{k} so as to maximize the sum ∑^{k}_{i}=_{1} ∑_{c∈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 ε > 0 and every fixed k our algorithm produces in linear time a solution whose value is within (1 - ε) 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.

Original language | English (US) |
---|---|

Pages (from-to) | 173-184 |

Number of pages | 12 |

Journal | Journal of Algorithms |

Volume | 33 |

Issue number | 1 |

DOIs | |

State | Published - Oct 1999 |

### All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'On Two Segmentation Problems'. Together they form a unique fingerprint.

## Cite this

*Journal of Algorithms*,

*33*(1), 173-184. https://doi.org/10.1006/jagm.1999.1024