0
$\begingroup$

Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:

1) Minimizing the number of balls that are required to cover all the points.

2) Maximizing the inter-clusters separation between clusters, which is define as follows:

For clusters $C_i$ and $C_j$ (with centroids $c_i$ and $c_j$), their inter-cluster separation $R_{ij}$ is $$ R_{ij}=\frac{d_{ij}}{(S_i+S_j)},$$ where $S_i=\Sigma_{p\in C_i} dist(c_i,p)$ and $d_{ij}=dist(c_i,c_j)$. (Here, $dist$ is the usual $l_2$-norm.)

The exact algorithm of the problem should output optimal centers ${c_1, c_2, ..}$ of the clusters.

I have following two questions regarding the problem:

1) What is the inherent complexity of the problem.

2) If the above problem can be solved in sublinear query/time (in a similar spirit of the learning problem in the PAC model)? More precisely, by querying $poly(\frac{1}{\epsilon}, logn)$ many positions from the input the algorithm should output approximated clusters, i.e. $\Sigma_i dist(c_i, c_{opt_i})<\epsilon$. (Here $c_{opt_i}$ is the center of $i^{th}$ optimal cluster.)

Pls let me know if there if I am able to put the question clearly.

Thanks!

Improve this question
$\endgroup$
6
  • $\begingroup$ The computational problem seems hard... But I don't see any connection to the PAC model, which involves seeing labeled examples and bounding some sort of generalization error/expected loss. How can you demand of a learner to get the labels right if he never gets to see any? $\endgroup$
    – Aryeh
    Commented Aug 13, 2014 at 15:33
  • 2
    $\begingroup$ Set cover by unit balls is NP-hard. Constant factor approximation is known in constant dimension. To recover clusters from a sample, you need some separation between the clusters. There are some results in this direction, see for example this paper cs.cmu.edu/~ninamf/papers/clustering-bbg-jacm.pdf. $\endgroup$
    – Sasho Nikolov
    Commented Aug 13, 2014 at 20:29
  • $\begingroup$ @Aryeh Sorry for the confusion. I intended to mean that can we put the above problem in the spirit of PAC learning framework, so that we can quantify sample size, approximation, probability confidence, model complexity (VC dimension) etc. Here, is a reference of a related work in that regard. www-faculty.cs.uiuc.edu/~pitt/Papers/soda-mop.pdf $\endgroup$
    – Ram
    Commented Aug 14, 2014 at 4:30
  • $\begingroup$ You have too many criterions. Either you are minimizing one quantity, or maximize the other, but doing both is usually as possible as seeing an invisible pink unicorn ;). In any case, sampling techniques tends to work in cases where the number of clusters is fixed (say k). If the number of clusters is unbounded things becomes significantly harder. A general bicriterion algorithm based on sampling is described in my paper "clustering motion", where it is used to speedup clustering algorithms (it can be interpeted as extending the paper by Lenny Pitt you are mentioning). $\endgroup$
    – Sariel Har-Peled
    Commented Aug 19, 2014 at 3:58
  • 1
    $\begingroup$ No. You can't. Consider the points being in one dimension - that is numbers. Assume the numbers are even integers (multiply them by 2). Deciding if you can cover them with n-1 unit intervals is equivalent to deciding if all the numbers are different. This is known as the uniqueness problem, and it is easy to see that you need to look on all the numbers (deterministically), or for a randomized algorithm, pick almost all the numbers into your random sample. The only hope is if you want to check if the numbers can be covered with k balls, and k is "small". $\endgroup$
    – Sariel Har-Peled
    Commented Aug 19, 2014 at 21:17

0

Reset to default

Your Answer

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