Email this article On the complexity of some problems of searching for a family of disjoint clusters
- Authors: Kel'manov A.V.1,2, Pyatkin A.V.1,2, Khandeev V.I.1,2
-
Affiliations:
- Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
- Novosibirsk State University
- Issue: Vol 484, No 4 (2019)
- Pages: 387-392
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/12540
- DOI: https://doi.org/10.31857/S0869-56524844387-392
- ID: 12540
Cite item
Full Text
Abstract
We consider some consimilar problems of searching for disjoint subsets (clusters) in the nite set of points in Euclidean space. In these problems, it is required to maximize the minimum subset size such that the value of each intracluster quadratic variation would not exceed a given fraction (constant) of the total quadratic variation of the points of the input set with respect to its centroid. In the paper, we have proved that all the problems are NP-hard even on a line.
About the authors
A. V. Kel'manov
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Author for correspondence.
Email: kelm@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090
A. V. Pyatkin
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Email: artem@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090
V. I. Khandeev
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University
Email: khandeev@math.nsc.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090
References
- Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean Sum-of-Squares clustering // Machine Learning. 2009. № 75 (2). Р. 245–248.
- Drineas P., Frieze A., Kannan R., Vempala S., Vinay V. Clustering Large Graphs via the Singular Value Decomposition // Machine Learning. 2004. № 56. Р. 9–33.
- Arora S., Raghavan P., Rao S. Approximation Schemes for Euclidean k-Medians and Related Problems. Proc. 30th Annual ACM Symposium on Theory of Computing. Dallas (TX), 1998. P. 106–113.
- Kariv O., Hakimi S. An Algorithmic Approach to Network Location Problems. Pt 1. The p-Centers // SIAM J. Appl. Math. 1979. V. 37. P. 513–538.
- Feder T., Greene D. Optimal Algorithms for Approximate Clustering. In: Proc. of the 20th ACM Symposium on Theory of Computing. N.Y., 1988. P. 434–444.
- Hochbaum D.S., Shmoys D.B. A Best Possible Heuristic for the k-Center Problem // Math. Operations Res. 1985. V. 10(2). P. 180–184.
- Kaufman L., Rousseeuw P.J. Clustering by Means of Medoids. In: Statistical Data Analysis Based on the L1-Norm and Related Methods. Amsterdam: North-Holland, 1987. P. 405–416.
- Krarup J., Pruzan P. The Simple Plant Location Problem: Survey and Synthesis // Europ. J. Oper. Res. 1983. № 12. V. (1). P. 36–81.
- Discrete Location Theory/Mirchandani P., Francis. R. Eds. L.: Wiley-Intersience, 1990.
- Charikar M., Khuller S., Mount D.M., Narasimhan G. Algorithms for Facility Location Problems with Outliers. In: Proc. 12th ACM-SIAM Symps. Discrete Algorithms. Wash. (D.C.), 2001. P. 642–651.
- Agarwal P.K., Phillips J.M. An Efficient Algorithm for 2D Euclidean 2-Center with Outliers. In: Proc. 16th Annu. European Sympos. Algorithms. Karlsruhe, 2008. P. 64–75.
- McCutchen R.M., Khuller S. Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. In: Proc. 11th Intern. Workshop Approx. Algorithms. Karlsruhe, 2008. P. 165–178.
- Hatami B., Zarrabi-Zade H. A Streaming Algorithm for 2-center with Outliers in High Dimensions // Comput. Geom. 2017. V. 60. P. 26–36.
- Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979.
Supplementary files
