Runtime dari algoritma approximation optimal greedy optimal untuk masalah -clustering

Kita diberi satu set titik 2 dimensi dan bilangan bulat . Kita harus menemukan kumpulan lingkaran yang melingkupi semua poin sehingga jari-jari lingkaran terbesar sekecil mungkin. Dengan kata lain, kita harus menemukan himpunan dari titik pusat k sehingga fungsi biaya \ text {cost} (C) = \ max_i \ min_j D (p_i, c_j ) diminimalkan. Di sini, D menunjukkan jarak Euclidean antara titik input p_i dan titik pusat c_j . Setiap titik menempatkan dirinya ke pusat kelompok terdekat yang mengelompokkan simpul menjadi kk k n C = { c 1 , c 2 , ... , c k } k biaya ( C ) = max i min j D ( p i , c j ) D p i c j$|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$ cluster yang berbeda.

Masalahnya dikenal sebagai masalah ( -crete ) $k$ -clustering dan itu adalah $\text{NP}$ -hard. Hal ini dapat ditunjukkan dengan pengurangan dari $\text{NP}$ set {NP} -lengkap set masalah mendominasi bahwa jika ada algoritma $\rho$ -approximation untuk masalah dengan $\rho < 2$ lalu $\text{P} = \text{NP}$ .

Algoritma $2$ approximation optimal sangat sederhana dan intuitif. Yang pertama mengambil titik $p \in P$ sewenang-wenang dan menempatkannya di set $C$ pusat cluster. Kemudian seseorang memilih pusat gugus berikutnya sehingga sejauh mungkin dari semua pusat gugus lainnya. Jadi sementara $|C| < k$ , kita berulang kali menemukan titik $j \in P$ yang jarak $D(j,C)$ dimaksimalkan dan menambahkannya ke $C$ . Sekali $|C| = k$ kita sudah selesai.

Tidak sulit untuk melihat bahwa algoritma serakah optimal berjalan dalam waktu $O(nk)$ . Hal ini menimbulkan pertanyaan: kita dapat mencapai $o(nk)$ waktu? Seberapa jauh lebih baik yang bisa kita lakukan?

Masalahnya memang bisa dilihat secara geometris dengan cara yang kita ingin menutupi titik dengan bola , di mana jari-jari bola terbesar diminimalkan.$V$$k$

$O(nk)$ memang cukup sederhana untuk dicapai tetapi orang dapat melakukan lebih baik. Feder dan Greene, algoritma optimal untuk pengelompokan perkiraan, 1988 mencapai waktu berjalan menggunakan struktur data yang lebih pintar dan lebih jauh menunjukkan bahwa ini optimal dalam model pohon keputusan aljabar.$\Theta(n \log k)$

Pertanyaan saya: Apakah ada cara saya dapat membuat strategi memetik serakah berjalan di waktu?$o(|V|^2)$

Sepertinya Anda menggambarkannya. Jika saya membaca deskripsi Anda terlalu jauh, inilah yang saya mengerti. Memiliki struktur data asosiatif menghubungkan setiap elemen dengan jumlah jarak ke elemen S . Struktur data ini dapat diinisialisasi dengan biaya O ( | V | ) dengan jarak ke p dan inisialisasi ini dapat menghasilkan elemen berikutnya sebagai efek samping tanpa meningkatkan kompleksitas. Ini dapat diperbarui setelah pemilihan elemen baru dengan biaya O ( | V | ) , lagi-lagi menghasilkan elemen berikutnya sebagai efek samping. Ulangi untuk mendapatkan $V$$S$$O(|V|)$$p$$O(|V|)$$S$. Kompleksitas yang dihasilkan adalah .$O(k |V|)$