Том 21, номер 3, 2014 г., Стр. 41-52

УДК 519.16+519.85
Кельманов А. В., Романченко С. М.
FPTAS для одной задачи поиска подмножества векторов

Аннотация:
Рассматривается NP-трудная в сильном смысле задача поиска в конечном множестве векторов евклидова пространства подмножества заданной мощности, доставляющего минимум сумме квадратов расстояний от элементов подмножества до его центра. Центр искомого подмножества определяется как cреднее значение вектора по всем элементам подмножества. Доказано, что если P ≠ NP, то для общего случая этой задачи не существует полностью полиномиальной приближённой схемы (FPTAS). Для специального случая этой задачи, когда размерность пространства фиксирована, такая схема обоснована.
Библиогр. 12.

Ключевые слова: поиск подмножества векторов, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, полностью полиномиальная приближённая схема.

Кельманов Александр Васильевич ^1,2
Романченко Семён Михайлович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, rsm@math.nsc.ru

Статья поступила 11 ноября 2013 г.
Исправленный вариант — 29 января 2014 г.

Литература

[1] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, №5. - С. 37–45.
Kel’manov A. V., Pyatkin А. V. NP-completeness of some problems of choosing a vector subset // J. Appl. Industr. Math. - 2011. - Vol. 5, N3. - P. 352–357.

[2] Кельманов А. В., Романченко С. М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №1. - С. 61–69.
Kel’manov A. V., Romanchenko S. M. An approximation algorithm for solving a problem of search for a vector subset // J. Appl. Industr. Math. - 2012. - Vol. 6, N1. - P. 90–96.

[3] Кельманов А. В., Романченко С. М. Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика. - 2012. - № 2. - С. 156–162.
Kel’manov A. V., Romanchenko S. M. Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems // Automation and Remote Control. - 2012. - Vol. 73, N2. - P. 349–354.

[4] Шенмайер В. В. Аппроксимационная схема для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №2. - С. 92–100.
Shenmaier V. V. An approximation scheme for a problem of search for a vector subset // J. Appl. Industr. Math. - 2012. - Vol. 6, N3. - P. 381–386.

[5] Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Les Cahiers du GERAD, G-2008-33. - 2008. - 4 p.

[6] Anil K. Jain K. Data clustering: 50 years beyond k-means // Pattern Recogn. Lett. - 2010. - Vol. 31. - P. 651–666.

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

[8] Hastie T., Tibshirani R., Friedman J. The elements of statistical learning: data mining, inference, and prediction. - New York: Springer-Verl., 2001. - 533 p.

[9] MacQueen J. B. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Math. Statist. Probab. (Berkeley, June 21–July 18, 1965; December 27, 1965–January 7, 1966). Vol. 1. - Berkeley: University of California Press, 1967. - P. 281–297.

[10] Papadimitriou C. H. Computational complexity. - New York: Addison-Wesley, 1994. - 523 p.

[11] Rao M. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. - 1971. - Vol. 66. - P. 622–626.

[12] Wirth Н. Algorithms + data structures = programs. - New Jersey: Prentice Hall, 1976. - 366 p.