Том 27, номер 2, 2020 г., Стр. 5-16

УДК 519.254
Борисова И. А.
Вычислительная сложность задачи выбора типичных представителей в 2-разбиении конечного множества точек метрического пространства

Аннотация:
Исследуется вычислительная сложность одной экстремальной задачи выбора подмножества $p$ точек в заданном 2-разбиении конечного множества точек метрического пространства. При этом требуется, чтобы выбранное подмножество наилучшим образом описывало определяемые 2-разбиением кластеры с точки зрения некоторого геометрического критерия. Рассматриваемая задача является формализацией одной прикладной проблемы из анализа данных, заключающейся в отыскании подмножества типичных представителей выборки, состоящей из объектов двух классов с опорой на функцию конкурентного сходства. В статье доказывается, что рассматриваемая задача NP-трудна. Для этого к ней полиномиально сводится одна из хорошо известных NP-трудных в сильном смысле задач — задача о $p$-медиане.
Библиогр. 15.

Ключевые слова: NP-трудная задача, выбор типичных объектов, функция конкурентного сходства, задача о $p$-медиане, анализ данных.

DOI: 10.33048/daio.2020.27.631

Борисова Ирина Артёмовна ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: biamia@mail.ru

Статья поступила 10 сентября 2018 г.
После доработки — 24 декабря 2019 г.
Принята к публикации 19 февраля 2020 г.

Литература

[1] Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman. 1979.

[2] Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Mach. Learn. 2009. Vol. 75, No. 2. P. 245–248.

[3] Dasgupta S. The hardness of k-means clustering. Tech. Rep. CS2007-0890. Univ. California, 2008. P. 1–6.

[4] Papadimitriou C. H. Worst-case and probabilistic analysis of a geometric location problem // SIAM J. Comput. 1981. Vol. 10, No. 3. P. 542–557.

[5] Har-Peled S., Mazumdar S. Coresets for k-means and k-median clustering and their applications // Proc. 36th Annu. ACM Sympos. Theory Comput. 2004. P. 291–300.

[6] Kaufman L., Rousseeuw P. J. Clustering by means of Medoids // Statistical data analysis based on the L1-norm and related methods (Y. Dodge, ed.). Amsterdam: North Holland. 1987. P. 405–416.

[7] Кельманов А. В., Пяткин А. В., Хандеев В. И. О сложности некоторых максиминных задач кластеризации // Тр. Ин-та математики и механики УрО РАН. 2018. Т. 24, № 4. C. 189–198.

[8] Кельманов А. В., Пяткин А. В. NP-трудность некоторых евклидовых задач разбиения конечного множества точек // Журн. вычисл. математики и мат. физики. 2018. Т. 58, № 5. C. 852–856.

[9] Aggarwal H., Imai N., Katoh N., Suri S. Finding k points with minimum diameter and related problems // J. Algorithms. 1991. Vol. 12, No. 1. P. 38–56.

[10] Zukhba A. V. NP-completeness of the problem of prototype selection in the nearest neighbor method // Pattern Recognit. Image Anal. 2010. Vol. 20, No. 4. P. 484–494.

[11] Banerjee S., Bhore S., Chitnis R. Algorithms and hardness results for nearest neighbor problems in bicolored point sets // Proc. 13th Latin Amer. Theor. Informatics Symposium (LATIN). 2018. P. 80–93.

[12] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.

[13] Burges C. J. C. A Tutorial on support vector machines for pattern recognition // Data Mining Knowl. Discov. 1998. Vol. 2, No. 2. P. 121–167.

[14] Zagoruiko N. G., Borisova I. A., Dyubanov V. V., Kutnenko O. A. Methods of recognition based on the function of rival similarity // Pattern Recognit. Image Anal. 2008. Vol. 18, No. 1. P. 1–6.

[15] Kariv O., Hakimi S. An algoritmic approach to network location problems. The $p$-medians // SIAM J. Appl. Math. 1979. Vol. 37. P. 539–560.