TY - JOUR
T1 - On Two Segmentation Problems
AU - Alon, Noga
AU - Sudakov, Benny
N1 - Funding Information:
The hypercube segmentation problem is the following: Given a set S of m vertices of the discrete d-dimensional cube 0, 14d, find k vertices P1,..., Pk, Pi g 0, 14d and a partitions of S into k segments S1,..., Sk so as to maximize the sum Ýis1k ÝcgSi Pi(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 y ϵ ) 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 s NP. Q 1999 Academic Press * Research supported in part by a USA—Israeli BSF grant, by the Minerva Center for Geometry at Tel Aviv University, by Sloan Foundation Grant 96-6-2, and by a State of New Jersey grant.
PY - 1999/10
Y1 - 1999/10
N2 - 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 P1,..., Pk, Pi ∈ {0, 1}d and a partitions of S into k segments S1,..., Sk so as to maximize the sum ∑ki=1 ∑c∈Si Pi⊙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.
AB - 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 P1,..., Pk, Pi ∈ {0, 1}d and a partitions of S into k segments S1,..., Sk so as to maximize the sum ∑ki=1 ∑c∈Si Pi⊙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.
UR - http://www.scopus.com/inward/record.url?scp=0038046968&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0038046968&partnerID=8YFLogxK
U2 - 10.1006/jagm.1999.1024
DO - 10.1006/jagm.1999.1024
M3 - Article
AN - SCOPUS:0038046968
SN - 0196-6774
VL - 33
SP - 173
EP - 184
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -