<p>Recently, I came across the following survey: <a href="https://link.springer.com/chapter/10.1007/978-981-10-6147-9_1" rel="nofollow noreferrer">Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems</a></p>
<p>The authors only discuss the major results and mention some interesting open problems at the end.</p>

CC BY-SA 4.0
2020-07-09T04:14:30.457Z
2020-07-09T04:14:30.457Z
Inuyasha Yagami
<p>I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:</p>
<ol>
<li><p>Space: Euclidean/metric/discrete/continuous/non-metric/2-D_plane...</p>
</li>
<li><p>Parameters: when <span class="math-container">$k$</span> or <span class="math-container">$d$</span> is fixed or some sort of bi-critera relaxation ...</p>
</li>
<li><p>Settings: Streaming/Online/parallel/Fault-tolerant/query/...</p>
</li>
<li><p>Constrained models: capacitated/outlier/fairness-constraints/...</p>
</li>
<li><p>Special models: <span class="math-container">$\beta$</span>-separation/ORSS-separability/BBG-condition/...</p>
</li>
<li><p>Techniques: coreset-based/primal-dual/local-search/distance-sampling/tree-decomposition/...</p>
</li>
<li><p>...many more</p>
</li>
</ol>
<p>There are several hardness results, approximation algorithm and parameterized algorithms known for the problem and its variants; and many are not known yet and are open.</p>
<p>Sometimes it happens that the research papers mention imprecise/incomplete/incorrect results, that have been previously discovered. This causes a lot of confusion. Moreover, it is difficult to go through every paper and check their results. I am looking for a (survey) paper that might give a brief idea of what all has been done in the field over the years and what are the open questions remaining in the field. It would be a great help if somebody could share such a paper.</p>

CC BY-SA 4.0
2020-07-01T01:45:05.093Z
I have a chapter in my book (geometric approximation algorithms) on clustering, that might be a good introduction for some of the more basic stuff.   But generally speaking  this is a huge topic, with active research. Furthermore, the non-theoretical side of clustering is huge - arguably all of ML can be formulated as various clustering problems.  Clustering is essentially the question of what is similar and what is different. Seems like large fraction of human knowledge....
Sariel Har-Peled
CC BY-SA 4.0
2020-07-09T09:49:17.243Z
https://mathoverflow.net/q/362135/10446 - Yet another question on K means, motivating that question: https://mathoverflow.net/q/362326/10446
Alexander Chervov
<reference-request><approximation-algorithms><approximation-hardness><clustering>
Good Survey paper for k-means/k-median/k-center/facility-location
Inuyasha Yagami
# Good Survey paper for k-means/k-median/k-center/facility-location

(Asked by: username_0 on 2020-06-23)

I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:

1. Space: Euclidean/metric/discrete/continuous/non-metric/2-D\_plane...
2. Parameters: when $k$ or $d$ is fixed or some sort of bi-critera relaxation ...
3. Settings: Streaming/Online/parallel/Fault-tolerant/query/...
4. Constrained models: capacitated/outlier/fairness-constraints/...
5. Special models: $\beta$-separation/ORSS-separability/BBG-condition/...
6. Techniques: coreset-based/primal-dual/local-search/distance-sampling/tree-decomposition/...
7. ...many more

There are several hardness results, approximation algorithm and parameterized algorithms known for the problem and its variants; and many are not known yet and are open.

Sometimes it happens that the research papers mention imprecise/incomplete/incorrect results, that have been previously discovered. This causes a lot of confusion. Moreover, it is difficult to go through every paper and check their results. I am looking for a (survey) paper that might give a brief idea of what all has been done in the field over the years and what are the open questions remaining in the field. It would be a great help if somebody could share such a paper.

**Tags:** reference-request, approximation-algorithms, approximation-hardness, clustering

> **Comments:**
> **username_1**: I have a chapter in my book (geometric approximation algorithms) on clustering, that might be a good introduction for some of the more basic stuff.   But generally speaking  this is a huge topic, with active research. Furthermore, the non-theoretical side of clustering is huge - arguably all of ML can be formulated as various clustering problems.  Clustering is essentially the question of what is similar and what is different. Seems like large fraction of human knowledge....  
> **username_2**: https://mathoverflow.net/q/362135/10446 - Yet another question on K means, motivating that question: https://mathoverflow.net/q/362326/10446  

---

## 1 answers

### Answer by username_0 on 2020-07-09. Score: 2

Recently, I came across the following survey: [Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems](https://link.springer.com/chapter/10.1007/978-981-10-6147-9_1)

The authors only discuss the major results and mention some interesting open problems at the end.


---

