<p>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:</p>

<p>1) Minimizing the number of balls that are required to cover all the points.</p>

<p>2) Maximizing the <em>inter-clusters separation</em> between clusters, which is define as follows:</p>

<p>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.)</p>

<p>The exact algorithm of the problem should output <em>optimal</em> centers ${c_1, c_2, ..}$ of the clusters. </p>

<p>I have following two questions regarding the problem:</p>

<p>1) What is the inherent complexity of the problem.</p>

<p>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, <em>i.e.</em> $\Sigma_i dist(c_i, c_{opt_i})&lt;\epsilon$. (Here $c_{opt_i}$ is the center of $i^{th}$ optimal cluster.)</p>

<p>Pls let me know if there if I am able to put the question clearly.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2014-08-13T15:33:59.257Z
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?
Aryeh
CC BY-SA 3.0
2014-08-13T20:29:13.553Z
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 http://www.cs.cmu.edu/~ninamf/papers/clustering-bbg-jacm.pdf.
Sasho Nikolov
CC BY-SA 3.0
2014-08-14T04:30:00.407Z
@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. http://www-faculty.cs.uiuc.edu/~pitt/Papers/soda-mop.pdf
Ram
CC BY-SA 3.0
2014-08-19T03:58:16.550Z
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).
Sariel Har-Peled
CC BY-SA 3.0
2014-08-19T05:06:42.937Z
@SarielHar-Peled, Dear Sariel, Thanks for your comment. Suppose for the easy case when we don't need to maximize the inter-cluster separation, we only need to minimize the number of balls that are required to cover the points. Then can we approximate the clusters in subliear (poly (\frac{1}{\epsilon}, \log n)) many queries with reasonable probability confidence.

-Regards
 Ram
Ram
CC BY-SA 3.0
2014-08-19T21:17:59.687Z
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".
Sariel Har-Peled
<approximation-algorithms><clustering><computational-geometry>
Clustering in sublinear time/query
Ram
# Clustering in sublinear time/query

(Asked by: username_0 on 2014-08-13)

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!

**Tags:** approximation-algorithms, clustering, computational-geometry

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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 http://www.cs.cmu.edu/~ninamf/papers/clustering-bbg-jacm.pdf.  
> **username_0**: @username_1 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. http://www-faculty.cs.uiuc.edu/~pitt/Papers/soda-mop.pdf  
> **username_3**: 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).  
> **username_0**: @SarielHar-Peled, Dear Sariel, Thanks for your comment. Suppose for the easy case when we don't need to maximize the inter-cluster separation, we only need to minimize the number of balls that are required to cover the points. Then can we approximate the clusters in subliear (poly (\frac{1}{\epsilon}, \log n)) many queries with reasonable probability confidence.  -Regards  username_0  
> **username_3**: 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".  

---

## 0 answers

