Wir erhalten eine Menge zweidimensionaler Punkte und eine ganze Zahl . Wir müssen eine Sammlung von Kreisen finden, die alle Punkte so einschließen, dass der Radius des größten Kreises so klein wie möglich ist. Mit anderen Worten, wir müssen eine Menge von Mittelpunkten finden, so dass die Kostenfunktion wird minimiert. Hier bezeichnet den euklidischen Abstand zwischen einem Eingabepunkt und einem Mittelpunkt . Jeder Punkt ordnet sich dem nächstgelegenen Cluster-Zentrum zu und gruppiert die Eckpunkte ink k n C = { c 1 , c 2 , … , c k } k Kosten ( C ) = max i min j D ( p i , c j ) D p i c j k verschiedene Cluster.
Das Problem ist als (diskretes) Clustering-Problem bekannt und es ist -hart. Es kann mit einer Reduktion von der gezeigt wird -komplette dominierende Menge Problem , dass , wenn es existiert ein -Approximationsalgorithmus für das Problem mit dann .NP NP ρ ρ < 2 P = NP
Der optimale Approximationsalgorithmus ist sehr einfach und intuitiv. Man wählt zunächst willkürlich einen Punkt und setzt ihn in die Menge der Clusterzentren. Dann wählt man das nächste Clusterzentrum so aus, dass es so weit wie möglich von allen anderen Clusterzentren entfernt ist. Also während , so finden wir immer wieder einen Punkt für die der Abstand maximiert wird , und fügen Sie . Einmal wir sind fertigp ∈ P C | C | < K j ∈ P D ( j , C ) C | C | = k
Es ist nicht schwer zu erkennen, dass der optimale Greedy-Algorithmus in wird. Dies wirft die Frage auf: Können wir Zeit erreichen? Wie viel besser können wir tun?o ( n k )