О псевдополиномиальной разрешимости квадратичной евклидовой задачи поиска семейства непересекающихся подмножеств
А.Е. Галашов1, А.В. Кельманов1,2
1Новосибирский национальный исследовательский государственный университет, ул. Пирогова, 2, Новосибирск, 630090 galashov.alexandr@gmail.com 2Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук kelm@math.nsc.ru
Ключевые слова: поиск подмножеств, кластерный анализ, евклидово пространство, минимум суммы квадратов расстояний, NP-трудная задача, точный псевдополинимиальный алгоритм, Euclidean space, subsets search, clustering, NP-hard problem, exact pseudopolynomial-time algorithm
Страницы: 15-22
Аннотация
Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве точек евклидова пространства семейства непересекающихся подмножеств, имеющих заданные мощности. Критерием решения задачи является минимум суммы по всем подмножествам сумм квадратов расстояний от элементов подмножеств до их геометрических центров. Доказано, что задача разрешима за псевдополиномиальное время, если координаты входных точек целочисленны, а размерность пространства и число искомых подмножеств фиксированы (ограничены константами).
DOI: 10.15372/SJNM20170102 |