K-merkezi

Sorun k -Centre ( k-merkez problemi İngilizce) olan sorun ait kombinatoryal optimizasyon , bir kolu algoritması . Sorun gayri resmi olarak şu şekilde tanımlanabilir: n kasabada verildiğinde , her kasaba ile en yakın itfaiye istasyonu arasındaki mesafenin en aza indirilmesi için k kasabada bir itfaiye istasyonu açmak gerekir .

Daha resmi olarak, bir dizi V noktası verildiğinde , bu, V noktalarından en yakın merkeze olan mesafelerin maksimumunun en aza indirileceği şekilde, merkez adı verilen bir k noktası alt kümesinin seçilmesi sorunudur . Çoğu durumda, örtük olarak uzayın metrik olduğunu düşünürüz , daha sonra sorun , kenarları üçgen eşitsizliğe göre ağırlıklara sahip bir grafikte doğal olarak bir problem olarak ifade edilir .

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. Kurulum yerleşiminden farklı bir uygulama, veri bölümlemedir (kümeleme) .

Resmi tanımlama

Sorun, metrik durumda aşağıdaki şekilde ifade edilir.

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 . $\ max _ {{v \ in V}} \ min _ {{s \ in S}} d (v, s)$ $\ min _ {{S \ subseteq V: | S | = k}} \ max _ {{v \ in V}} \ min _ {{s \ in S}} d (v, s)$

Metrik olmayan genel durum çok az incelenmiştir çünkü yaklaşım açısından bile çok zordur. Daha doğrusu, varsayım olmadan sorun APX'te değildir . Makalenin geri kalanı örtük olarak metrik durumu ele alır.

Karmaşıklık

Sorun, karar problemi versiyonunda NP-tamamlandı .

Yaklaşıklık

Var oranı 2 yaklaşık algoritmalar ve eğer p NP farklıdır bu sonuç en uygunudur.

Açgözlü algoritma

Aşağıdaki açgözlü algoritma Bazen denir 1985 yılında Gonzalez tarafından önerilmiştir en uzak ilk geçişi .

Keyfi bir ilk tepe noktası seçin ve onu bir merkez yapın.
Do k-1 defa:
- Merkezlere olan mesafesi maksimum olan bir tepe noktası bulun
- Bir merkez yapın.

Hesaplanan çözüm, en kötü durumda, optimal çözümün yarısı kadar iyidir. Hızla kanıtlıyoruz. Algoritmanın sonunda bir noktadan merkeze maksimum uzaklık r ve p böyle bir nokta olsun. S , merkezlerden ve p'den oluşan küme olsun . S kümesi birbirinden en az r k + 1 puana sahiptir . O zaman optimal çözümde, en az iki S noktası aynı merkezi paylaşmalıdır (S'de optimal çözümde merkezlerden daha fazla nokta vardır). Üçgen eşitsizliğe göre, aynı merkezi paylaşan bu noktalardan en az biri, bir merkezden r / 2 uzaklıktadır.

Zaman karmaşıklığı algoritması olan O (nk) .

Eşik yöntemi

Eşik yöntemiyle bir 2 yaklaşımı elde edebiliriz ( parametrik budama olarak da adlandırılır ). Olası tüm çözümlerin test edilmesinden oluşur: optimum değer, bir uçta mevcut olan bir maliyettir, kenarların sayısı polinomdur ve her değer için bir polinom testi yapabiliriz. Test, daha büyük ağırlıktaki kenarların kaldırılmasından ve budanmış grafikte 2-yaklaşım elde edip edemeyeceğimizin kontrol edilmesinden oluşur.

Bu algoritma Hochbaum ve Shmoys'tan kaynaklanmaktadır.

Yaklaşım zorluğu

Problem NP- 2'den küçük bir oran için yaklaşılması zordur . Bu sonuç Hsu ve Nemhauser'den kaynaklanmaktadır. Aşağıda verilen kanıt , baskın küme problemine bir indirgemedir .

Baskın küme problemi için bir örnek (G, k) olsun . Bunu , kenarlarda aşağıdaki ağırlıklarla aynı köşelere sahip olan bir G ' örneğine dönüştürüyoruz : G'nin kenarları için 1 ve diğerleri için 2. Baskın grubu daha az boyutta ise k o G ' eksiksiz 1' in bir k-merkez çözeltisi, böylece maliyet 2. 2'den daha az ise oranda bir yaklaşım algoritması, aksi takdirde bir çözümü vardır, baskın grubu problemine yanıt verir ki kendisi NP-zordur .

Özel durumlar

Grafik düzlemsel ise , problem için bir polinom zaman yaklaşım şeması vardır .

Varyantlar, ilgili sorunlar ve uygulamalar

Özel bir durum, metriğin bazen geometrik k-merkezi olarak adlandırılan Öklid olduğu durumdur .

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-medyan problemi aynı çerçeveyi kullanır, ancak en aza 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- merkezinin hesaplanması, verileri bölümlere ayırmayı mümkün kılabilir . Mesafeler, k-ortalamalarında olduğu gibi 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 .
Samir Khuller ve Yoram J. Sussmann, " Kapasiteye Sahip \ vurgu {K} -Merkez Sorunu ", SIAM J. Discrete Math. , cilt. 13, n o 3, 2000, s. 403-418
Dorit S Hochbaum, "Çeşitli yaklaşım kavramları: İyi, daha iyi, en iyi ve daha fazlası" , NP-zor problemler için yaklaşım algoritmalarında , PWS Publishing Co., 1996, s. 346-446
(in) Michael Garey ve David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
(en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ve Gerhard Woeginger, " Metric k-center " , NP optimizasyon problemlerinin A özeti üzerine ,2000.
Teofilo F. Gonzalez , " Kümeler arası maksimum mesafeyi en aza indirmek için kümeleme ", Teorik Bilgisayar Bilimi , cilt. 38, 1985, s. 293-306 ( DOI 10.1016 / 0304-3975 (85) 90224-5 )
(en) Sanjoy Dasgupta, " Ders 1: Metrik uzaylarda kümeleme " , San Diego'daki California Üniversitesi ,2013
Jack Edmonds ve Delbert Ray Fulkerson , " Darboğaz ekstrema " Journal of Combinatorial Theory , cilt. 8, n o 3, 1970, s. 299-306.
(en) Vijay Vazirani , Yaklaşım algoritmaları , Springer Verlag , 2001 (sonra 2003), 380 s. ( ISBN 978-3-540-65367-7 ) , böl. 5 ("k-merkezi")
Thomas Rothvoss'un " Yaklaşım Algoritması " adlı 14-19. Slaytlarına bakınız ,2009.
Dorit S. Hochbaum ve David B. Shmoys , " K-Merkezi Problemi için Olası En İyi Sezgisel Yöntem ", Yöneylem Araştırması Matematiği , cilt. 10, n o 2 1985, s. 180-184
Wen-Lian Hsu ve George L. Nemhauser, " Kolay ve zor darboğaz konum problemleri ", Discrete Applied Mathematics , Elsevier, cilt. 1, n o 3, 1979, s. 209-215
David Eisenstat, Philip N. Klein ve Claire Mathieu, "Yaklaşık k- merkezini düzlemsel grafiklerde" , Yirmi Beşinci Yıllık ACM-SIAM Sempozyumu Ayrık Algoritmalar Bildirilerinde, SODA 2014, Portland, Oregon, ABD, 5 Ocak 7, 2014 , 2014, s. 617-627
David P. Williamson ve David B. Shmoys, böl. 2.2 "The Design of Approximation Algorithms , Cambridge University Press içinde " k-merkezi sorunu "

Dış bağlantılar

(tr) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ve Gerhard Woeginger , " Metric k-center " , A compendium of NP optimization issues ,2000.
(tr) Sanjoy Dasgupta, " Ders 1: Metrik uzaylarda kümeleme " , California Üniversitesi, San Diego ,2013