K-medyan

K -median sorun veya k-medyan İngilizce, bir olan kombinatoryal optimizasyon problemi , bir kolu algoritmalarıyla . Sorun olarak aşağıda gayri tarif edilebilir: Verilen n şehirler, bir mağaza açmak için gerekli olan k ki şehirlerde böyle ortalama şehirler ve onların en yakın mağazalar arasındaki mesafeleri en aza indirilir. K-araçları sorununa yakın olan bu sorun, diğer şeylerin yanı sıra verileri bölümlemeye izin verir .

Sorunun resmileştirilmesi aşağıdaki gibidir. Noktaları bir dizi Verilen V , bir alt kümesini seçmek k noktalarından gelen noktaların mesafelerin ortalaması şekilde adlandırılan merkezleri, V en yakın merkeze en aza indirilir. Sorun çoğunlukla bir metrik uzayda ifade edilir . Daha sonra , kenarları üçgen eşitsizliğe göre ağırlıklara sahip bir grafikte doğal olarak bir problem olarak ifade edilir . Zirvelerin iki kategoriye ayrıldığını da düşünebiliriz: çalışma zirveleri ve kapsayacak zirveler.

Bu problem esas olarak yaklaşım açısından incelenmiştir . En aza indirilmesi gereken belirli ölçüler veya diğer maliyetler gibi çeşitli varyasyonlar vardır.

Resmi tanımlama

Sorun şu şekilde ifade edilmektedir.

Bir tamsayı k ve tam bir grafik yönsüz G = ( V , E ) verildiğinde, d ( v i , v j ) ∈ N mesafesi üçgen eşitsizliğine göre, | ile bir S ⊆ V alt kümesi bulun. S | = K aza indirir o: . Başka bir deyişle, kimin optimizasyon problemi düşünün amaç fonksiyonu olduğunu . $\ toplam _ {v \ in V} \ min _ {s \ in S} d (v, s)$ $\ min _ {S \ subseteq V: | S | = k} \ sum _ {v \ in V} \ min _ {s \ in S} d (v, s)$

Yaklaşıklık

K- median problemi , metrik durumda bile NP-zordur . Metrik durumda yaklaşım için yeterince büyük bir literatüre sahiptir (genel durum APX'te değildir ).

Doğrusal optimizasyon ve yerel arama dahil olmak üzere çeşitli yöntemler kullanılmıştır .

Varyantlar, ilgili sorunlar ve uygulamalar

Sorunu değiştirmenin klasik bir yolu, merkezlere farklı kapasiteler eklemektir. Bu nedenle, belirli bir düğüm merkez olarak seçilirse, yalnızca sınırlı sayıda komşuya hizmet edebilir.

K-merkezi problemi aynı çerçeveyi kullanır, ancak asgariye indirilecek başka bir işlevle. Gelen tesislerin yeri sorununa ( tesis yeri problemi ), biz parametre yerine k açılması ve bağlantı maliyetleri.

Bir k- median hesaplaması, verileri bölümlemek için kullanılabilir . Mesafeler daha sonra benzerlikleri temsil eder.

Notlar ve referanslar

Fransızca çevirisi Nicolas Shabanel'in (en) Vijay Vazirani'nin çevirisinden gelmektedir , Yaklaşım algoritmaları , Springer Verlag , 2001 (sonra 2003), 380 s. ( ISBN 978-3-540-65367-7 ) Bkz “ : içindekiler Yaklaşım algoritmaları ” üzerine, Nicolas Schabanel sitesinde .
Kamal Jain ve Vijay Vazirani , " Primal-dual şemayı ve Lagrangian gevşemesini kullanarak metrik tesis konumu ve k-medyan problemleri için yaklaşım algoritmaları, " Journal of the ACM (JACM) , cilt. 48, n o 2 2001, s. 274-296
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala ve Vinayaka Pandit, " k-medyan ve tesis konum problemleri için yerel arama sezgisel tarama ", SIAM Journal on Computing , cilt. 33, n o 3, 2004, s. 544-562

Dış bağlantılar

(tr) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ve Gerhard Woeginger , NP optimizasyon problemlerinin bir özeti üzerine " Minimum k-medyan " ,2000.
David Dohan, Stefani Karp, Brian Matejek, “ K-medyan Algoritmalar: Teori Uygulamada ” , üzerinde gelen kursu Gelişmiş algoritmalar Sanjeev Arora de Stanford Üniversitesi .