Том 23, номер 3, 2016 г., Cтр. 21–34

УДК 519.16 + 519.85
Кельманов А. В., Моткова А. В.
Точные псевдополиномиальные алгоритмы для задачи сбалансированной 2-кластеризации

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

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

DOI: 10.17377/daio.2016.23.520

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

Статья поступила 25 мая 2016 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14, № 1. С. 32–42.

[2] Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985. 360 p.

[3] Гимади Э. Х., Глазков Ю. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммы размерности // Дискрет. анализ и исслед. опер. 2008. Т. 15, № 4. С. 30–43.

[4] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб.
журн. индустр. математики. 2006. Т. 9, № 1. С. 55–74.

[5] Долгушев А. В., Кельманов А. В. Приближённый алгоритм решения одной задачи кластерного анализа // Дискрет. анализ и исслед. опер. 2011. Т. 18, № 2. С. 29–40.

[6] Долгушев А. В., Кельманов А. В., Шенмайер В. В. Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера // Тр. Ин-та математики и механики УрО РАН. 2015. Т. 21, № 3. С. 100–109.

[7] Кельманов А. В., Пяткин А. В. NP-трудность некоторых квадратичных евклидовых задач 2-кластеризации // Докл. АН. 2015. Т. 464, № 5. С. 535–538.

[8] Кельманов А. В., Пяткин А. В. О сложности некоторых квадратичных евклидовых задач 2-кластеризации // Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 3. С. 150–156.

[9] Кельманов А. В., Романченко С. М. Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика. 2012. № 2. С. 156–162.

[10] Кельманов А. В., Романченко С. М. FPTAS для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 41–52.

[11] Кельманов А. В., Хандеев В. И. Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного анализа // Дискрет. анализ и исслед. опер. 2013. Т. 20, № 4. С. 36–45.

[12] Кельманов А. В., Хандеев В. И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Журн. вычисл. математики и мат. физики. 2015. Т. 55, № 2. С. 335–344.

[13] Кельманов А. В., Хандеев В. И. Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов // Дискрет. анализ и исслед. опер. 2015. Т. 22, № 3. С. 36–48.

[14] 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.

[15] Brucker P. On the complexity of clustering problems // Optimization and Operations Research. Proc. Workshop Held Univ. Bonn (Bonn, Germany, Oct. 2–8, 1977). Heidelberg: Springer-Verl., 1978. P. 45–54. (Lect. Notes Econom. Math. Systems; Vol. 157).

[16] De la Vega W. F., Karpinski M., Kenyon C., Rabani Y. Polynomial time approximation schemes for metric min-sum clustering // Electron. Colloq. Comput. Complexity (ECCC), Report No. 25. Potsdam: Hasso-Plattner-Inst. Softwaresystemtechnik, 2002.

[17] De la Vega W. F., Kenyon C. A randomized approximation scheme for metric Max-Cut // J. Comput. Syst. Sci. 2001. Vol. 63. P. 531–541.

[18] Fisher R. A. Statistical methods and scientific inference. New York: Hafner Press, 1959. 350 p.

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

[20] Gimadi E. Kh., Kel’manov A. V., Kel’manova M. A., Khamidullin S. A. A posteriori detecting a quasiperiodic fragment in a numerical sequence // Pattern Recognit. Image Anal. 2008. Vol. 18, No. 1. P. 30–42.

[21] Hasegawa S., Imai H., Inaba M., Katoh N., Nakano J. Efficient algorithms for variance-based k-clustering // Proc. 1st Pac. Conf. Comput. Graphics Appl. (Seoul, Korea, Aug. 30 – Sept. 2, 1993). River Edge, NJ: World Scientific, 1993. Vol. 1. P. 75–89.

[22] Inaba M., Katoh N., Imai H. Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering // Proc. 10th Symp. Comput. Geom. (Stony Brook, NY, USA, June 68, 1994). New York: ACM,1994. P. 332–339.

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

[24] Sahni S., Gonzalez T. P-complete approximation problems // J. ACM. 1976. Vol. 23. P. 555–566.