Понедельник, 12 ноября, ауд. 106. Начало в 14:00.
Докладчик: Кирилл Симонов (Университет Бергена).
Тема: Параметризованная сложность задачи k-means.
Abstract
k-means кластеризация -- это следующая задача: по данным n точкам в
![$ R^d $](/sites/default/files/tex/d5191a248fbf72037dbd5d89ba848be19d3f9f67.png)
найти k центров кластеров так, чтобы минимизировать сумму расстояний от точек до ближайших к ним центрам кластеров. Задача получила широкую известность благодаря применениям в data mining, и в особенности эвристическому алгоритму Ллойда. Известно, что найти
оптимальную кластеризацию NP-трудно даже при d=2 или k=2, в то же время существует алгоритм со временем работы
![$ n^{O(dk)} $](/sites/default/files/tex/2a1fd24b617d5a9d1f9ef9751367cc49016846da.png)
. Мы впервые рассматриваем задачу k-means с точки зрения параметризованной сложности, где целью является либо нахождение алгоритма со временем
работы
![$ f(t)n^{O(1)} $](/sites/default/files/tex/46b30f402081119f75f3b94d9b4abd2d3f0d1bd0.png)
для некоторого параметра задачи t, либо доказательство невозможности его существования при условии FPT≠W[1]. Рассматриваемые нами параметры для k-means -- это k, d и искомое расстояние D (при условии, что входные данные целочисленные).
Используя алгоритм для быстрого нахождения подгиперграфа с малым fractional cover number, мы получаем FPT-алгоритм по D для
![$ L_1 $](/sites/default/files/tex/08cc13ed87bff7952961903282ab4515e215c3de.png)
-расстояния. Интересно, что в случае расстояния в
![$ L_2 $](/sites/default/files/tex/2d7807df86324711850f93bf6d27d3d52a7e9b22.png)
задача ощутимо труднее — мы показываем, что одна из подзадач, возникающая в нашем алгоритме, является здесь W[1]-трудной. Мы также обобщаем эти результаты на
![$ L_p $](/sites/default/files/tex/14cff1542794b415c532abfa8fcbfd57c510157e.png)
для остальных значений p, и даем нижние оценки для некоторых комбинаций параметров в экстремальных случаях
![$ L_0 $](/sites/default/files/tex/788a6d4422354b7f3bf9128522b9dccbc77e2b7f.png)
and
![$ L_\infty $](/sites/default/files/tex/7c75a0e50474c5169c458fa34afb2383229cc2e3.png)
. Отдельный интерес может представлять набор используемых нами сведений, позволяющих представить стандартные комбинаторные задачи на графах как геометрические задачи кластеризации.