Отправить статью по E-mail О сложности некоторых задач поиска семейства непересекающихся кластеров
- Авторы: Кельманов А.В.1,2, Пяткин А.В.1,2, Хандеев В.И.1,2
-
Учреждения:
- Институт математики им. С.Л. Соболева Сибирского отделения Российской Академии наук
- Новосибирский государственный университет
- Выпуск: Том 484, № 4 (2019)
- Страницы: 387-392
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/12540
- DOI: https://doi.org/10.31857/S0869-56524844387-392
- ID: 12540
Цитировать
Полный текст
Аннотация
Рассматриваются две родственные задачи поиска семейства непересекающихся подмножеств (кластеров) в конечном множестве точек евклидова пространства. В этих задачах требуется максимизировать размер минимального по мощности кластера так, чтобы в каждом кластере суммарный внутрикластерный квадратичный разброс точек не превышал заданной доли (константы) от суммарного квадратичного разброса точек во входном множестве. Доказано, что обе задачи NP-трудны даже на числовой прямой.
Ключевые слова
Об авторах
А. В. Кельманов
Институт математики им. С.Л. Соболева Сибирского отделения Российской Академии наук; Новосибирский государственный университет
Автор, ответственный за переписку.
Email: kelm@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
А. В. Пяткин
Институт математики им. С.Л. Соболева Сибирского отделения Российской Академии наук; Новосибирский государственный университет
Email: artem@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
В. И. Хандеев
Институт математики им. С.Л. Соболева Сибирского отделения Российской Академии наук; Новосибирский государственный университет
Email: khandeev@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
Список литературы
- 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.
Дополнительные файлы
