Home

Понедельник 12.11. Кирилл Симонов: "Параметризованная сложность задачи k-means"

Понедельник, 12 ноября, ауд. 106. Начало в 14:00.

Докладчик: Кирилл Симонов (Университет Бергена).

Тема: Параметризованная сложность задачи k-means.

Abstract

k-means кластеризация -- это следующая задача: по данным n точкам в $ R^d $ найти k центров кластеров так, чтобы минимизировать сумму расстояний от точек до ближайших к ним центрам кластеров. Задача получила широкую известность благодаря применениям в data mining, и в особенности эвристическому алгоритму Ллойда. Известно, что найти
оптимальную кластеризацию NP-трудно даже при d=2 или k=2, в то же время существует алгоритм со временем работы $ n^{O(dk)} $. Мы впервые рассматриваем задачу k-means с точки зрения параметризованной сложности, где целью является либо нахождение алгоритма со временем
работы $ f(t)n^{O(1)} $ для некоторого параметра задачи t, либо доказательство невозможности его существования при условии FPT≠W[1]. Рассматриваемые нами параметры для k-means -- это k, d и искомое расстояние D (при условии, что входные данные целочисленные).

Используя алгоритм для быстрого нахождения подгиперграфа с малым fractional cover number, мы получаем FPT-алгоритм по D для $ L_1 $-расстояния. Интересно, что в случае расстояния в $ L_2 $ задача ощутимо труднее — мы показываем, что одна из подзадач, возникающая в нашем алгоритме, является здесь W[1]-трудной. Мы также обобщаем эти результаты на $ L_p $ для остальных значений p, и даем нижние оценки для некоторых комбинаций параметров в экстремальных случаях $ L_0 $ and $ L_\infty $. Отдельный интерес может представлять набор используемых нами сведений, позволяющих представить стандартные комбинаторные задачи на графах как геометрические задачи кластеризации.