# Good Survey paper for k-means/k-median/k-center/facility-location

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.

• 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.... Jul 1 '20 at 1:45
• mathoverflow.net/q/362135/10446 - Yet another question on K means, motivating that question: mathoverflow.net/q/362326/10446 Jul 9 '20 at 9:49