Время выполнения оптимального алгоритма жадной

$|P| = n$$k$$k$$n$$C = \{ c_1,c_2,\ldots,c_k\}$$k$$\text{cost}(C) = \max_i \min_j D(p_i, c_j)$$D$обозначает евклидово расстояние между входной точкой и центральной точкой . Каждая точка присваивается ближайшему центру кластера, группируя вершины в различных кластеров.$p_i$$c_j$$k$

Эта проблема известна как (дискретная) проблема кластеризации и является -hard. С помощью задачи -комплектного доминирующего множества можно показать, что если для задачи с существует алгоритм -approximation, то .NP NP ρ ρ < 2 P = $k$$\text{NP}$$\text{NP}$$\rho$$\rho < 2$$\text{P} = \text{NP}$

Оптимальный алгоритм приближения очень прост и интуитивно понятен. Сначала произвольно выбирают точку и помещают ее в множество центров кластеров. Затем выбирают следующий кластерный центр так, чтобы он был как можно дальше от всех других кластерных центров. Так что пока , мы неоднократно находим точку , для которых расстояние максимизируется и добавить его в . Однажды мы сделали.p ∈ P $2$$p \in P$$C$$|C| < k$$j \in P$$D(j,C)$$C$$|C| = k$

Нетрудно видеть, что оптимальный жадный алгоритм выполняется за времени. Возникает вопрос: можем ли мы достичь времени? Насколько лучше мы можем сделать?o ( n k $O(nk)$$o(nk)$

Проблему действительно можно рассматривать геометрически так, чтобы мы хотели покрыть точек k шарами, где радиус наибольшего шара минимизирован.$V$$k$

действительно довольно просто достичь, но можно добиться большего. Федер и Грин, Оптимальные алгоритмы приближенной кластеризации, 1988,достигают времени выполнения Θ ( n log k ), используя более умные структуры данных, и далее показывают, что это оптимально в алгебраической модели дерева решений.$O(nk)$$\Theta(n \log k)$

Мой вопрос: есть ли способ заставить жадную стратегию выбора работать за время?$o(|V|^2)$

Мне кажется, что вы это описали. Если я читаю слишком далеко в вашем описании, вот что я понял. Иметь ассоциативную структуру данных , связывающую каждый элемент с суммой расстояния до элементов S . Эта структура данных может быть инициализирована по стоимости O ( | V | ) с расстоянием до p, и эта инициализация может создать следующий элемент как побочный эффект без увеличения сложности. Он может быть обновлен после выбора нового элемента по цене O ( | V | ) , снова создавая следующий элемент в качестве побочного эффекта. Повторите, чтобы получить $V$$S$$O(|V|)$$p$$O(|V|)$$S$, Результирующая сложность .$O(k |V|)$