0
$\begingroup$

Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$.

Each point $p$ defines a set $B_p$ (or a ball) that covers all other points that lie within a distance $r$ from $p$. Find $k$ sets (or balls) that covers the most number of points.

Obviously, we could find a $1-1/e$ approximation (via greedy) as this is a special case of the maximum $k$-set coverage problem.

But is there a hardness result for this problem? I would also like to consider the Euclidean distance case.

Improve this question
$\endgroup$
2
  • $\begingroup$ There is a PTAS, at least in 2d arxiv.org/abs/1702.01836 $\endgroup$
    – Sasho Nikolov
    Oct 17, 2017 at 9:23
  • 2
    $\begingroup$ If one can get better than (1-1/e) for your problem you can get the same bound for max k-coverage in arbitrary set systems - consider the reduction of set cover to dominating set in a graph. $\endgroup$
    – Chandra Chekuri
    Oct 17, 2017 at 12:53

2 Answers 2

Reset to default
2
$\begingroup$

The problem of covering $n$ points in the Euclidean plane by $k$ unit balls is a special case of your problem that is already known to be NP-complete. It is also hard to approximate the optimal covering radius better than a factor of about 1.84. See

N. Megiddo and K.J. Supowit. On the complexity of some common geometric loca- tion problems. SIAM J. Comput., 13:182–196, 1984.

T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985.

T. Feder and D.H. Greene. Optimal algorithms for approximate clustering. In Proc.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think the OP is asking a different question. He is given k balls of fixed radius r and wants to maximize the # of points covered. $\endgroup$
    – Chandra Chekuri
    Oct 18, 2017 at 0:46
  • 1
    $\begingroup$ True, but if you can't solve the decision problem (can you cover all points) you also can't solve the optimization problems (how many can you cover, or what radius do you need to cover all). $\endgroup$
    – David Eppstein
    Oct 18, 2017 at 17:51
1
$\begingroup$

For the case of disks in the plane, there is a recent PTAS: https://arxiv.org/abs/1607.06665 There is also a fixed parameter tractable algorithm for this problem for spaces with bounded VC dimension - see ref in the paper.

For general metric spaces, it is easy to reduce the problem to set cover instance, where there is a cover with k sets covering m points, iff there are k balls covering m points. To see that, just take the set system, and build a bipartite graph, with ground elements on one side, and sets on the other side. Connect every set, to every element it covers. All edges have weight 1, and all missing edges, are assigned their shortest path distance. Clearly, in this graph, there is a coverage by k balls (of radius 1) of m points iff there are k sets covering m elements in the original set system. since 1-1/e approximation to partial set cover is the best one can hope for (I am too lazy to find the ref - but that should be well known), it follows that it is not possible in general to do better.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.