6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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.... $\endgroup$
    – Sariel Har-Peled
    Jul 1, 2020 at 1:45
  • $\begingroup$ mathoverflow.net/q/362135/10446 - Yet another question on K means, motivating that question: mathoverflow.net/q/362326/10446 $\endgroup$
    – Alexander Chervov
    Jul 9, 2020 at 9:49

1 Answer 1

Reset to default
2
$\begingroup$

Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems

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

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.