Name
Abstract | ||
|---|---|---|
We study the \LowerBoundedCenter (\lbc) problem, which is a clustering problem that can be viewed as a variant of the \kCenter problem. In the \lbc problem, we are given a set of points P in a metric space and a lower bound \lambda, and the goal is to select a set C \subseteq P of centers and an assignment that maps each point in P to a center of C such that each center of C is assigned at least \lambda points. The price of an assignment is the maximum distance between a point and the center it is assigned to, and the goal is to find a set of centers and an assignment of minimum price. We give a constant factor approximation algorithm for the \lbc problem that runs in O(n \log n) time when the input points lie in the d-dimensional Euclidean space R^d, where d is a constant. We also prove that this problem cannot be approximated within a factor of 1.8-\epsilon unless P = \NP even if the input points are points in the Euclidean plane R^2. |
Year | Venue | Field |
|---|---|---|
2013 | CoRR | Discrete mathematics,Binary logarithm,Approximation algorithm,Combinatorics,Upper and lower bounds,Euclidean space,Euclidean geometry,Metric space,Cluster analysis,Mathematics,Lambda |
DocType | Volume | Citations |
Journal | abs/1304.7318 | 7 |
PageRank | References | Authors |
0.45 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alina Ene | 1 | 409 | 25.47 |
| Sariel Har-Peled | 2 | 2630 | 191.68 |
| Benjamin Raichel | 3 | 36 | 9.01 |