Отправить статью по E-mail 
NP-полнота некоторых задач разбиения конечного множества точек евклидова пространства на сбалансированные кластеры
- Авторы: Кельманов А.В.1,2, Пяткин А.В.1,2, Хандеев В.И.1,2
-
Учреждения:
- Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук
- Новосибирский государственный университет
- Выпуск: Том 488, № 1 (2019)
- Страницы: 16-20
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/16157
- DOI: https://doi.org/10.31857/S0869-5652488116-20
- ID: 16157
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассматриваются три родственные между собой задачи разбиения N-элементного множества точек d-мерного евклидова пространства на два кластера так, чтобы сбалансировать значения: (1) внутрикластерного квадратичного разброса, нормированного на размер кластера, в первой задаче; (2) внутрикластерного квадратичного разброса, во второй задаче; (3) мощностно-взвешенного внутрикластерного разброса, в третьей задаче. Доказано, что все эти задачи 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. V. 75. № 2. P. 245-248.
- Papadimitriou C.H. // Worst-Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput. 1981. V. 10. № 3. P. 542-557.
- Masuyama S., Ibaraki T., Hasegawa T. // The computational complexity of the m-center problems in the plane. IEEE Trans. IECE Jpn. 1981. V. 64. № 2. P. 57-64.
- Aggarwal H., Imai N., Katoh N., Suri S. // Finding k points with minimum diameter and related problems. J. Algorithms. 1991. V. 12. № 1. P. 38-56.
- Snedecor G.W., Cochran W.G. // Statistical Methods, Eighth Edition, Iowa State University Press, 1989.
- Garey M.R., Johnson D.S. // Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. San Francisco, 1979.
Дополнительные файлы
