Понедельник, 12 ноября, ауд. 106. Начало в 14:00.
Докладчик: Кирилл Симонов (Университет Бергена).
Тема: Параметризованная сложность задачи k-means.
Abstract
k-means кластеризация -- это следующая задача: по данным n точкам в

найти k центров кластеров так, чтобы минимизировать сумму расстояний от точек до ближайших к ним центрам кластеров. Задача получила широкую известность благодаря применениям в data mining, и в особенности эвристическому алгоритму Ллойда. Известно, что найти
оптимальную кластеризацию NP-трудно даже при d=2 или k=2, в то же время существует алгоритм со временем работы

. Мы впервые рассматриваем задачу k-means с точки зрения параметризованной сложности, где целью является либо нахождение алгоритма со временем
работы

для некоторого параметра задачи t, либо доказательство невозможности его существования при условии FPT≠W[1]. Рассматриваемые нами параметры для k-means -- это k, d и искомое расстояние D (при условии, что входные данные целочисленные).
Используя алгоритм для быстрого нахождения подгиперграфа с малым fractional cover number, мы получаем FPT-алгоритм по D для

-расстояния. Интересно, что в случае расстояния в

задача ощутимо труднее — мы показываем, что одна из подзадач, возникающая в нашем алгоритме, является здесь W[1]-трудной. Мы также обобщаем эти результаты на

для остальных значений p, и даем нижние оценки для некоторых комбинаций параметров в экстремальных случаях

and

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