Środowisko uruchomieniowe optymalnego algorytmu chciwości

$|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$oznacza odległość euklidesową między punktem wejściowym a punktem środkowym . Każdy punkt przypisuje się do najbliższego centrum gromady grupującego wierzchołki w różnych skupisk.c j$p_i$$c_j$$k$

Problem znany jest jako (dyskretny) problem klastrowania i jest to -hard. Można to pokazać z redukcją problemu kompletnego dominującego problemu, że jeśli istnieje algorytm aproksymacji dla problemu z to .NP NP ρ ρ < 2 P = $k$$\text{NP}$$\text{NP}$$\rho$$\rho < 2$$\text{P} = \text{NP}$

Optymalny algorytm aproksymacji jest bardzo prosty i intuicyjny. Najpierw wybiera arbitralnie punkt i umieszcza go w zbiorze centrów skupień. Następnie wybiera się kolejne centrum klastrów, które jest możliwie jak najdalej od wszystkich pozostałych centrów klastrów. Więc póki , my wielokrotnie znaleźć punkt , dla których odległość D (j, C) jest zmaksymalizowane i dodać go do C . Raz | C | = k skończone.p ∈ P C | C | < k j ∈ P D ( j , C ) C | C | = $2$$p \in P$$C$$|C| < k$$j \in P$$D(j,C)$$C$$|C| = k$

Nietrudno zauważyć, że optymalny algorytm zachłanny działa w czasie $O(nk)$ . Rodzi to pytanie: czy możemy osiągnąć czas $o(nk)$ ? O ile lepiej możemy zrobić?

Problem można rzeczywiście rozpatrywać geometrycznie w taki sposób, że chcielibyśmy objąć punkty kulkami, w których promień największej kuli jest zminimalizowany.$V$$k$

$O(nk)$ jest rzeczywiście dość proste do osiągnięcia, ale można zrobić lepiej. Feder i Greene, Optymalne algorytmy przybliżonego grupowania, 1988 osiągają czas działania przy użyciu bardziej sprytnych struktur danych i dalej pokazują, że jest to optymalne w algebraicznym modelu drzewa decyzyjnego.$\Theta(n \log k)$

Moje pytanie: Czy istnieje sposób, aby uruchomić chciwą strategię kompletacji w czasie ?$o(|V|^2)$

Wydaje mi się, że to opisałeś. W przypadku, gdy przeczytałem zbyt daleko w twoim opisie, oto co zrozumiałem. Posiada strukturę danych asocjacyjny przypisujące każdy element przy czym suma odległości od elementów S . Ta struktura danych może być inicjowana kosztem O ( | V | ) z odległością do p, a ta inicjalizacja może wytworzyć następny element jako efekt uboczny bez zwiększania złożoności. Można go zaktualizować po wybraniu nowego elementu kosztem O ( | V | ) , ponownie wytwarzając kolejny element jako efekt uboczny. Powtórz, aby uzyskać $V$$S$$O(|V|)$$p$$O(|V|)$$S$. Wynikająca z tego złożoność to .$O(k |V|)$