Tesis konumu sorunu - Facility location problem - Wikipedia

Çalışma tesis konum sorunları (FLP), Ayrıca şöyle bilinir konum analizi, bir dalı yöneylem araştırması ve hesaplamalı geometri Tehlikeli maddeleri barınakların ve rakiplerin tesislerinin yakınına yerleştirmekten kaçınmak gibi faktörleri göz önünde bulundururken nakliye maliyetlerini en aza indirmek için tesislerin en uygun şekilde yerleştirilmesiyle ilgilenir. Teknikler ayrıca şunlar için de geçerlidir: küme analizi.

Minimum tesis konumu

Basit bir tesis konumu sorunu, Weber sorunu tek bir tesisin yerleştirileceği, tek optimizasyon kriteri belirli bir nokta alanlarından ağırlıklı toplam mesafelerin en aza indirilmesidir. Bu disiplinde ele alınan daha karmaşık sorunlar, birden çok tesisin yerleştirilmesini, tesislerin konumlarına ilişkin kısıtlamaları ve daha karmaşık optimizasyon kriterlerini içerir.

Temel bir formülasyonda, tesis yeri sorunu bir dizi potansiyel tesis sahasından oluşur L bir tesisin açılabileceği yer ve bir dizi talep noktası D servise verilmesi gerekir. Amaç, bir alt küme seçmektir F açılacak tesislerin sayısı, her talep noktasından en yakın tesisine olan mesafelerin toplamı artı tesislerin açılış maliyetlerinin toplamı.

Genel grafiklerde tesis konumu sorunu şudur: NP-zor en uygun şekilde çözmek için (örneğin) kapak sorunu ayarla. Tesis lokasyon problemi ve birçok varyantı için bir dizi yaklaşık algoritma geliştirilmiştir.

Müşteriler ve siteler arasındaki mesafeler hakkında varsayımlar olmaksızın (özellikle, mesafelerin, üçgen eşitsizliği ), sorun olarak bilinir metrik olmayan tesis yeri ve bir O faktörü dahilinde tahmin edilebilir (logn).^[1] Bu faktör, bir yaklaşıklığı koruyan azaltma set kapak probleminden.

İstemciler ve siteler arasındaki mesafelerin yönsüz olduğunu varsayarsak ve üçgen eşitsizliğini giderirsek, bir metrik tesis konumu (MFL) sorun. MFL hala NP-zordur ve 1,463'ten daha iyi faktör dahilinde yaklaşması zordur.^[2] Şu anda en iyi bilinen yaklaşım algoritması, 1.488'lik yaklaşım oranına ulaşmaktadır.^[3]

Minimax tesis yeri

minimax tesis yeri problem, bir noktadan sitelere olan mesafenin noktadan en yakın yere olan mesafeyi oluşturduğu, sitelere maksimum mesafeyi en aza indiren bir konum arar. Resmi bir tanım aşağıdaki gibidir: Bir nokta kümesi verildiğinde P ⊂ ℝ^d, bir puan seti bul S ⊂ ℝ^d, |S| = k, böylece maksimum_p ∈ P(dk_q ∈ S(d (p, q))) küçültülür.

Öklid metriği durumunda k = 1 olarak bilinir en küçük çevreleyen küre sorun veya 1 merkez sorunu. Çalışması en azından 1860 yılına kadar uzanıyordu. Bkz. en küçük çevreleyen daire ve sınırlayıcı küre daha fazla ayrıntı için.

NP sertliği

Kesin çözüm olduğu kanıtlanmıştır. k-merkez problem NP zordur.^[4]^[5]^[6]Hata küçük olduğunda soruna yaklaşımın da NP zor olduğu bulundu. Hata düzeyi yaklaşım algoritması yaklaşım ve optimum arasındaki oran olarak tanımlanan bir yaklaşım faktörü olarak ölçülür. Kanıtlandı k-merkez problem yaklaşımı, yaklaşım faktörü 1.822'den küçük olduğunda (boyut = 2) NP zordur^[7] veya 2 (boyut> 2).^[6]

Algoritmalar

Tam çözücü

Bu soruna kesin çözümler üretmek için algoritmalar mevcuttur. Tam bir çözücü zamanında çalışır ${ displaystyle n ^ {O ({ sqrt {k}})}}$ .^[8]^[9]

1 + ε yaklaşım

1 + ε yaklaşıklık, yaklaşım faktörü 1 + 'dan büyük olmayan bir çözüm bulmaktır.ε. Bu yaklaşım NP zordur. ε keyfi. Temel alan bir yaklaşım çekirdek konsept, uygulama karmaşıklığı ile önerilmiştir ${ displaystyle O (2 ^ {O (k log k / varepsilon ^ {2})} dn)}$ .^[10]Alternatif olarak, çekirdek setlerine dayalı başka bir algoritma da mevcuttur. İçeri giriyor ${ displaystyle O (k ^ {n})}$ .^[11] Yazar, çalışma süresinin en kötü durumdan çok daha az olduğunu ve bu nedenle bazı sorunları çözmenin mümkün olduğunu iddia ediyor. k küçük (söylek < 5).

En uzak nokta kümeleme

Problemin sertliği için, kesin bir çözüm veya kesin bir yaklaşım elde etmek pratik değildir. Bunun yerine, faktör = 2 ile bir yaklaşım, büyük için yaygın olarak kullanılır. k durumlarda. Yaklaşım, en uzak nokta kümeleme (FPC) algoritması olarak adlandırılır veya en uzaktaki ilk geçiş.^[6] Algoritma oldukça basittir: Kümedeki herhangi bir noktayı tek bir merkez olarak seçin; başka bir merkez olarak kalan setten en uzak noktayı arayın; işlemi tekrarlayın k merkezleri bulunur.

Bu algoritmanın doğrusal zamanda çalıştığını görmek kolaydır. Faktör 2'den küçük olan yaklaşımın NP sert olduğu kanıtlandığından, FPC bulunabilecek en iyi yaklaşım olarak kabul edildi.

Yürütme performansına göre, zaman karmaşıklığı daha sonra O (n günlükk) kutu ayrıştırma tekniği ile.^[7]

Maxmin tesis konumu

maxmin tesis konumu veya iğrenç tesis yeri problem, sitelere olan minimum mesafeyi maksimize eden bir konum arar. Öklid metriği durumunda, bu, en büyük boş küre sorun. Düzlemsel durum (en büyük boş daire problem) çözülebilir en uygun zaman Θ (n log n).^[12]^[13]

Tamsayı programlama formülasyonları

Tesis konum sorunları genellikle şu şekilde çözülür: tamsayı programları. Bu bağlamda, tesis konum sorunları genellikle şu şekilde ortaya çıkar: ${ displaystyle n}$ tesisler ve ${ displaystyle m}$ müşteriler. Aşağıdakilerden hangisini seçmek istiyoruz (1) ${ displaystyle n}$ açılacak tesisler ve (2) hangi (açık) tesisler ${ displaystyle m}$ Müşteriler, bazı sabit talepleri minimum maliyetle karşılamak için. Şu gösterimi tanıtıyoruz: let ${ displaystyle f_ {i}}$ açılış tesisinin (sabit) maliyetini belirtir ${ displaystyle i}$ , için ${ displaystyle i = 1, noktalar, n}$ . İzin Vermek ${ displaystyle c_ {ij}}$ tesisten bir ürün sevk etmenin maliyetini belirtir ${ displaystyle i}$ müşteriye ${ displaystyle j}$ için ${ displaystyle i = 1, noktalar, n}$ ve ${ displaystyle j = 1, noktalar, m}$ . İzin Vermek ${ displaystyle d_ {j}}$ müşterinin talebini belirtmek ${ displaystyle j}$ için ${ displaystyle j = 1, noktalar, m}$ . Ayrıca, her tesisin bir maksimum çıktıya sahip olduğunu varsayalım. İzin Vermek ${ displaystyle u_ {i}}$ tesis tarafından üretilebilecek maksimum ürün miktarını gösterir ${ displaystyle i}$ yani izin ver ${ displaystyle u_ {i}}$ belirtmek kapasite tesisin ${ displaystyle i}$ . Bu bölümün geri kalanı aşağıdaki gibidir^[14]

Kapasiteye sahip tesis yeri

İlk formülümüzde bir ikili değişken ekleyin ${ displaystyle x_ {i}}$ için ${ displaystyle i = 1, noktalar, n}$ , nerede ${ displaystyle x_ {i} = 1}$ eğer tesis ${ displaystyle i}$ açık ve ${ displaystyle x_ {i} = 0}$ aksi takdirde. Değişkeni daha fazla tanıtın ${ displaystyle y_ {ij}}$ için ${ displaystyle i = 1, noktalar, n}$ ve ${ displaystyle j = 1, noktalar, m}$ talebin oranını temsil eden ${ displaystyle d_ {j}}$ tesis tarafından dolduruldu ${ displaystyle i}$ . Sözde kapasiteli tesis yeri sorunu tarafından verilir

{ displaystyle { begin {array} {rl} min & displaystyle sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {m} c_ {ij} d_ {j} y_ {ij} + sum _ {i = 1} ^ {n} f_ {i} x_ {i} { text {st}} & displaystyle sum _ {i = 1} ^ {n} y_ { ij} = 1 { text {tümü için}} j = 1, dots, m & displaystyle sum _ {j = 1} ^ {m} d_ {j} y_ {ij} leqslant u_ {i } x_ {i} { text {tümü için}} i = 1 dots, n & y_ {ij} geqslant 0 { text {tümü için}} i = 1, dots, n { text {ve }} j = 1, dots, m & x_ {i} in {0,1 } { text {tümü için}} i = 1, dots, n end {dizi}}}

İkinci kısıtlama kümesinin, ${ displaystyle x_ {i} = 0}$ yani tesis ${ displaystyle i}$ o zaman açık değil ${ displaystyle y_ {ij} = 0}$ hepsi için ${ displaystyle j}$ yani tesisten hiçbir müşteri talebi karşılanamaz ${ displaystyle i}$ .

Kapasitesi olmayan tesis yeri

Yukarıdaki kapasiteye sahip tesis konumu sorununun yaygın bir durumu, ${ displaystyle u_ {i} = + infty}$ hepsi için ${ displaystyle i = 1, noktalar, n}$ . Bu durumda, müşteriden gelen tüm talebi karşılamak her zaman en uygunudur. ${ displaystyle j}$ en yakın açık tesisten. Bu nedenle sürekli değişkenleri değiştirebiliriz ${ displaystyle y_ {ij}}$ yukarıdan ikili değişkenlerle ${ displaystyle z_ {ij}}$ , nerede ${ displaystyle z_ {ij} = 1}$ müşteri ise ${ displaystyle j}$ tesis tarafından sağlanır ${ displaystyle i}$ , ve ${ displaystyle z_ {ij} = 0}$ aksi takdirde. kapasitesiz tesis yeri sorunu tarafından verilir

{ displaystyle { begin {array} {rl} min & displaystyle sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {m} c_ {ij} d_ {j} z_ {ij} + sum _ {i = 1} ^ {n} f_ {i} x_ {i} { text {st}} & displaystyle sum _ {i = 1} ^ {n} z_ { ij} = 1 { text {tümü için}} j = 1, dots, m & displaystyle sum _ {j = 1} ^ {m} z_ {ij} leqslant Mx_ {i} { text {tümü için}} i = 1 nokta, n & z_ {ij} in {0,1 } { text {tümü için}} i = 1, dots, n { text {ve}} j = 1, dots, m & x_ {i} in {0,1 } { text {tümü için}} i = 1, dots, n end {dizi}}}

nerede ${ displaystyle M}$ uygun büyüklükte seçilmiş bir sabittir. Un seçimi ${ displaystyle M}$ hesaplama sonuçlarını etkileyebilir - bu durumda en iyi seçim açıktır: ${ displaystyle M = m}$ . O zaman eğer ${ displaystyle x_ {i} = 1}$ herhangi bir seçim ${ displaystyle z_ {ij}}$ ikinci kısıtlamaları karşılayacaktır.

Kapasitesi olmayan tesis yeri sorunu için başka bir formülasyon olasılığı, ayrıştırmak kapasite kısıtlamaları (büyük ${ displaystyle M}$ kısıtlamalar). Yani, kısıtlamaları değiştirin

{ displaystyle sum _ {j = 1} ^ {m} z_ {ij} leqslant Mx_ {i} { text {tümü için}} i = 1, noktalar, n}

kısıtlamalarla

{ displaystyle z_ {ij} leqslant x_ {i} { text {tümü için}} i = 1, dots, n { text {ve}} j = 1, dots, m}

Pratikte, bu yeni formülasyon daha sıkı olması anlamında önemli ölçüde daha iyi performans gösterir. Doğrusal programlama ilk formülasyondan daha gevşeme.^[14] Yeni kısıtlamaların bir araya toplanmasının orijinal büyük

{ displaystyle M}

kısıtlamalar. Kapasite edilmiş durumda, bu formülasyonlar eşdeğer değildir. Kapasitesi olmayan tesis konum sorunu hakkında daha fazla bilgi "Ayrık konum teorisi" Bölüm 3'te bulunabilir.^[15]

Kümeleme Uygulamaları

Belirli bir alt kümesi küme analizi sorunlar tesis yeri sorunları olarak görülebilir. Centroid tabanlı bir kümeleme probleminde amaç, ${ displaystyle n}$ veri noktaları (ortak bir metrik uzayın öğeleri) eşdeğerlik sınıflarına - genellikle denir renkler- aynı renkteki noktalar birbirine yakın olacak şekilde (eşdeğer olarak, farklı renkteki noktalar birbirinden uzak olacak şekilde).^[16]

Merkez tabanlı bir kümeleme problemini (metrik) bir tesis konum problemi olarak nasıl görülebileceğini ("dönüştürme" veya "azaltma" okunması) görmek için, ilkindeki her veri noktasını ikincisinde bir talep noktası olarak görün. Kümelenecek verilerin bir metrik alanın öğeleri olduğunu varsayalım ${ displaystyle M}$ (ör. izin ver ${ displaystyle M}$ olmak ${ displaystyle p}$ -boyutlu Öklid uzayı bazı sabitler için ${ displaystyle p}$ ). Kurmakta olduğumuz tesis lokasyon probleminde, tesislerin bu metrik uzay içerisinde herhangi bir noktaya yerleştirilmesine izin veriyoruz. ${ displaystyle M}$ ; bu izin verilen tesis konumlarını tanımlar ${ displaystyle L}$ . Maliyetleri biz belirliyoruz ${ displaystyle c _ { ell, d}}$ konum-talep nokta çiftleri arasındaki ikili mesafeler olmak (ör. bkz. metrik k-merkezi ). Centroid tabanlı bir kümeleme probleminde, verilerden biri veriyi ${ displaystyle k}$ her biri bir ağırlık merkezine sahip eşdeğerlik sınıfları (yani renkler). Yapılandırılan tesis lokasyon problemimize bir çözümün de böyle bir bölümü nasıl sağladığını görelim. Uygulanabilir bir çözüm, boş olmayan bir alt kümedir ${ displaystyle L ' subseteq L}$ nın-nin ${ displaystyle k}$ yerler. Tesisimizdeki bu konumlar konum problemi bir dizi ${ displaystyle k}$ centroid tabanlı kümeleme sorunumuzda centroidler. Şimdi, her bir talep noktasını atayın ${ displaystyle d}$ konuma ${ displaystyle ell ^ {*}}$ servis maliyetini en aza indiren; yani, veri noktasını atayın ${ displaystyle d}$ centroid'e ${ displaystyle ell ^ {*}: = mathrm {arg , min} _ { ell in L} {c _ { ell, d} }}$ (keyfi olarak bağları koparmak). Bu, tesis konumu sorununun maliyetleri olması şartıyla bölümlemeyi sağlar. ${ displaystyle c _ { ell, d}}$ ağırlık merkezi tabanlı kümeleme probleminin uzaklık fonksiyonunun görüntüleri olacak şekilde tanımlanmıştır.

Popüler algoritmalar ders kitabı Algoritma Tasarımı ^[17] ilgili bir problem tanımı ve bir tahmin algoritması sağlar. Yazarlar, metrik tesis konumu sorununa (yani, ağırlık merkezi tabanlı kümeleme sorunu veya metrik ${ displaystyle k}$ merkez problemi) olarak merkez seçim problemi, böylece eş anlamlılar listesi büyüyor.

Ayrıca, tesis konumu sorunu ile ilgili yukarıdaki tanımımızda, hedef işlevin ${ displaystyle f}$ geneldir. Özel seçimler ${ displaystyle f}$ tesis konum probleminin farklı varyantlarını ve dolayısıyla merkez tabanlı kümeleme probleminin farklı varyantlarını verir. Örneğin, her konumdan kendisine atanan talep noktalarının her birine olan mesafelerin toplamını en aza indirmeyi seçebilir (à la the Weber sorunu ) veya bu tür tüm mesafelerin maksimumunu en aza indirmeyi seçebilir (à la the 1 merkez sorunu ).

Sağlık tesisi yeri

Sağlık tesislerinin yerleştirilmesinde yerleşim sorunları yaygın olarak kullanılmaktadır. Son inceleme kağıdı ^[18] bu konu ile ilgili anket çalışmaları.

Ayrıca bakınız

Referanslar

^ Hochbaum, D. S. (1982). "Sabit maliyet medyan sorunu için buluşsal yöntemler". Matematiksel Programlama. 22: 148–162. doi:10.1007 / BF01581035.
^ Guha, S .; Khuller, S. (1999). "Greedy Strikes Back: Geliştirilmiş Tesis Yer Algoritmaları". Algoritmalar Dergisi. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006 / jagm.1998.0993.
^ Li, S. (2011). "Kapasitesi Olmayan Tesis Yerleşimi Problemi için 1.488 Yaklaşım Algoritması". Otomata, Diller ve Programlama. LNCS. 6756. sayfa 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.
^ Fowler, R. J .; Paterson, M. S .; Tanimoto, S. L. (1981), "Düzlemde optimum paketleme ve kaplama NP-tamamlanmıştır", Bilgi İşlem Mektupları, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.
^ Megiddo, Nemrut; Tamir, Arie (1982), "Düzlemde doğrusal tesisleri bulmanın karmaşıklığı hakkında" (PDF), Yöneylem Araştırma Mektupları, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.
^ ^a ^b ^c Gonzalez, Teofilo (1985), "Kümeler arası maksimum mesafeyi en aza indirmek için kümeleme" (PDF), Teorik Bilgisayar Bilimleri, 38: 293–306, doi:10.1016/0304-3975(85)90224-5, dan arşivlendi orijinal (PDF) 2013-01-24 tarihinde.
^ ^a ^b Feder, Tomás; Greene, Daniel (1988), "Yaklaşık kümeleme için en uygun algoritmalar", Yirminci Yıllık ACM Hesaplama Teorisi Sempozyumu Bildirileri: 434–444, doi:10.1145/62212.62255, ISBN 0897912640
^ HWang, R.Z .; Lee, R.C. T .; Chang, R. C. (1993), "Öklid p-merkezi problemini çözmek için döşeme bölme yaklaşımı", Algoritma, 9 (1): 1–22, doi:10.1007 / BF01185335
^ HWang, R.Z .; Chang, R. C .; Lee, R. C. T. (1993), "Alt üstel zamanda bazı NP-Hard problemlerini çözmek için ayırıcılar üzerinden genelleştirilmiş arama stratejisi", Algoritma, 9 (4): 398–423, doi:10.1007 / bf01228511
^ Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Çekirdek kümeler aracılığıyla yaklaşık kümeleme" (PDF), Bilgisayar Kuramı Üzerine Otuz Dördüncü Yıllık ACM Sempozyumu Bildirileri: 250–257, doi:10.1145/509907.509947, ISBN 1581134959
^ Kumar, Pankaj; Kumar, Piyush (2010), "K-kümeleme sorunlarına neredeyse optimal çözümler" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142 / S0218195910003372
^ Franco P. Preparata ve Michael Ian Shamos (1985). Hesaplamalı Geometri - Giriş. Springer-Verlag. ISBN 978-0-387-96131-6. 1. baskı; 2. baskı, düzeltilmiş ve genişletilmiş, 1988; Rusça çevirisi, 1989., s. 256
^ G. T. Toussaint, "Konum kısıtlamalarıyla en büyük boş dairelerin hesaplanması" Uluslararası Bilgisayar ve Bilişim Bilimleri Dergisi, cilt. 12, No. 5, Ekim 1983, s. 347–358.
^ ^a ^b Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Tamsayı Programlama | SpringerLink. Matematikte Lisansüstü Metinler. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.
^ Ayrık konum teorisi. Mirchandani, Pitu B., Francis, R.L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.CS1 Maint: diğerleri (bağlantı)
^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). İstatistiksel öğrenmenin unsurları (İkinci baskı). Springer.
^ Kleinberg, Jon; Tardos, Éva (2006). Algoritma Tasarımı. Pearson.
^ Ahmedi-Cavid, A .; Seyedi, P .; Syam, S. (2017). "Sağlık Tesisi Yerleşimi Üzerine Bir Araştırma". Bilgisayarlar ve Yöneylem Araştırması. 79: 223–263. doi:10.1016 / j.cor.2016.05.018.

Dış bağlantılar

EWGLA Lokasyon Analizi Üzerine EURO Çalışma Grubu.
BİLGİ VERİR konum analizi bölümü, tesis konumuyla ilgilenen profesyonel bir topluluk.
Tesis konumu hakkında kaynakça toplandı Trevor Hale, 3400'den fazla makale içeren.
Konum algoritmaları kütüphanesi
Web tabanlı tesis konumu yardımcı programı (tek tesis)
Tesis Konumu Optimize Edici, tesis konum problemlerini çözmek için MATLAB tabanlı bir araç.

[1] Hochbaum, D. S. (1982). "Sabit maliyet medyan sorunu için buluşsal yöntemler". Matematiksel Programlama. 22: 148–162. doi:10.1007 / BF01581035.

[2] Guha, S .; Khuller, S. (1999). "Greedy Strikes Back: Geliştirilmiş Tesis Yer Algoritmaları". Algoritmalar Dergisi. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006 / jagm.1998.0993.

[3] Li, S. (2011). "Kapasitesi Olmayan Tesis Yerleşimi Problemi için 1.488 Yaklaşım Algoritması". Otomata, Diller ve Programlama. LNCS. 6756. sayfa 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.

[4] Fowler, R. J .; Paterson, M. S .; Tanimoto, S. L. (1981), "Düzlemde optimum paketleme ve kaplama NP-tamamlanmıştır", Bilgi İşlem Mektupları, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.

[5] Megiddo, Nemrut; Tamir, Arie (1982), "Düzlemde doğrusal tesisleri bulmanın karmaşıklığı hakkında" (PDF), Yöneylem Araştırma Mektupları, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.

[Gonzalez1985-6] Gonzalez, Teofilo (1985), "Kümeler arası maksimum mesafeyi en aza indirmek için kümeleme" (PDF), Teorik Bilgisayar Bilimleri, 38: 293–306, doi:10.1016/0304-3975(85)90224-5, dan arşivlendi orijinal (PDF) 2013-01-24 tarihinde.

[Feder1988-7] Feder, Tomás; Greene, Daniel (1988), "Yaklaşık kümeleme için en uygun algoritmalar", Yirminci Yıllık ACM Hesaplama Teorisi Sempozyumu Bildirileri: 434–444, doi:10.1145/62212.62255, ISBN 0897912640

[8] HWang, R.Z .; Lee, R.C. T .; Chang, R. C. (1993), "Öklid p-merkezi problemini çözmek için döşeme bölme yaklaşımı", Algoritma, 9 (1): 1–22, doi:10.1007 / BF01185335

[9] HWang, R.Z .; Chang, R. C .; Lee, R. C. T. (1993), "Alt üstel zamanda bazı NP-Hard problemlerini çözmek için ayırıcılar üzerinden genelleştirilmiş arama stratejisi", Algoritma, 9 (4): 398–423, doi:10.1007 / bf01228511

[10] Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Çekirdek kümeler aracılığıyla yaklaşık kümeleme" (PDF), Bilgisayar Kuramı Üzerine Otuz Dördüncü Yıllık ACM Sempozyumu Bildirileri: 250–257, doi:10.1145/509907.509947, ISBN 1581134959

[11] Kumar, Pankaj; Kumar, Piyush (2010), "K-kümeleme sorunlarına neredeyse optimal çözümler" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142 / S0218195910003372

[ps256-12] Franco P. Preparata ve Michael Ian Shamos (1985). Hesaplamalı Geometri - Giriş. Springer-Verlag. ISBN 978-0-387-96131-6. 1. baskı; 2. baskı, düzeltilmiş ve genişletilmiş, 1988; Rusça çevirisi, 1989., s. 256

[13] G. T. Toussaint, "Konum kısıtlamalarıyla en büyük boş dairelerin hesaplanması" Uluslararası Bilgisayar ve Bilişim Bilimleri Dergisi, cilt. 12, No. 5, Ekim 1983, s. 347–358.

[:0-14] Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Tamsayı Programlama | SpringerLink. Matematikte Lisansüstü Metinler. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.

[15] Ayrık konum teorisi. Mirchandani, Pitu B., Francis, R.L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.CS1 Maint: diğerleri (bağlantı)

[16] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). İstatistiksel öğrenmenin unsurları (İkinci baskı). Springer.

[17] Kleinberg, Jon; Tardos, Éva (2006). Algoritma Tasarımı. Pearson.

[Ahmadi-18] Ahmedi-Cavid, A .; Seyedi, P .; Syam, S. (2017). "Sağlık Tesisi Yerleşimi Üzerine Bir Araştırma". Bilgisayarlar ve Yöneylem Araştırması. 79: 223–263. doi:10.1016 / j.cor.2016.05.018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]