K-senter

Problemet k- sentrum ( k- senterproblem på engelsk) er et problem med kombinatorisk optimalisering , en gren av algoritmen . Problemet kan beskrives uformelt som følger: gitt n byer er det nødvendig å åpne en brannstasjon i k byer, slik at avstanden mellom hver by og nærmeste brannstasjon minimeres.

Mer formelt er det et spørsmål, gitt et sett med punkter V , om å velge en delmengde av k- punkter, kalt sentre, slik at maksimum avstandene fra punktene V til nærmeste sentrum minimeres. I de fleste tilfeller vurderer vi implisitt at rommet er metrisk , og problemet blir da naturlig uttrykt som et problem på en graf hvis kanter har vekter som respekterer den trekantede ulikheten .

Dette problemet studeres hovedsakelig fra tilnærmingens synspunkt . Det er flere varianter, med spesifikke beregninger eller andre kostnader som skal minimeres. En annen applikasjon enn plasseringen av installasjoner er partisjonering av data (klynging) .

Formell definisjon

Problemet uttrykkes som følger i metrisk tilfelle.

Gitt et heltall k og en komplett graf under retning G = ( V , E ), avstanden d ( v i , v j ) ∈ N respekterer trekant ulikhet, finn en delmengde S ⊆ V med | S | = K som minimerer: . Med andre ord vurderer vi optimaliseringsproblemet hvis objektive funksjon er . $\ 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)$

Den generelle saken uten beregning er lite studert fordi den er for vanskelig selv fra synspunkt tilnærming. Mer presist, uten antagelse, er problemet ikke i APX . Resten av artikkelen behandler implisitt metrisk tilfelle.

Kompleksitet

Problemet er NP-komplett i sin beslutningsproblemversjon .

Tilnærming

Det er forhold 2 tilnærmelsesalgoritmer , og hvis P er forskjellig fra NP er dette resultatet optimalt.

Grådig algoritme

Den følgende grådig algoritme ble foreslått av Gonzalez i 1985. Det er noen ganger kalt lengst først traversering .

Velg et vilkårlig første toppunkt og gjør det til et senter.
Gjør k-1 ganger:
- Finn et toppunkt hvis avstand til sentre som allerede er åpne er maks
- Gjør det til et senter.

Den beregnede løsningen er i verste fall halvparten så god som den optimale løsningen. Vi beviser det raskt. På slutten av algoritmen, la r være den maksimale avstanden fra et punkt til et senter, og la p være et slikt punkt. La S være settet som består av sentre og s . Settet S har k + 1 poeng minst r fra hverandre. Så i den optimale løsningen, må minst to punkter av S dele det samme sentrum (det er flere poeng i S enn sentre i den optimale løsningen). I følge den trekantede ulikheten, er minst ett av disse punktene som deler det samme sentrum på avstand r / 2 fra et sentrum.

Den tid kompleksiteten av algoritmen er O (nk) .

Terskelmetode

Vi kan få en 2-tilnærming ved terskelmetoden ( også kalt parametrisk beskjæring ). Den består i å teste alle mulige løsninger: den optimale verdien er en kostnad til stede på en kant, antall kanter er polynom og vi kan gjøre en polynomtest for hver verdi. Testen består i å fjerne kantene med større vekt og kontrollere at vi kan få en 2-tilnærming i den beskjærte grafen.

Denne algoritmen skyldes Hochbaum og Shmoys.

Vanskelighetsgrad med tilnærming

Problemet er NP-vanskelig å nærme seg i et forhold mindre enn 2. Dette resultatet skyldes Hsu og Nemhauser. Beviset nedenfor er en reduksjon til det dominerende settproblemet .

La være en forekomst (G, k) for problemet med det dominerende settet. Vi forvandler det til en forekomst G ' , den komplette grafen har de samme hjørnene, med følgende vekter på kantene: 1 for kantene til G og 2 for de andre. Hvis det dominerende settet er av størrelse mindre enn k, har G ' en k-senterløsning av kostnad 1, ellers en løsning av kostnad 2. Dermed gir en tilnærmingsalgoritme med forhold mindre enn 2 svar på problemet med det dominerende settet som i seg selv er NP-hardt .

Spesielle tilfeller

Hvis grafen er plan , er det et polynomisk tilnærmingsskjema for problemet.

Varianter, relaterte problemer og applikasjoner

Et spesielt tilfelle er når beregningen er euklidisk , noen ganger kalt geometrisk k-senter .

En klassisk måte å endre problemet på er å legge til forskjellige kapasiteter til sentrene. Dermed kan en bestemt node, hvis den er valgt som sentrum, bare betjene et begrenset antall naboer.

K-median- problemet bruker samme rammeverk, men med en annen funksjon som skal minimeres. I lokaliseringsproblemet til anlegg ( anleggslokalitetsproblem ) erstatter vi parameteren k med kostnadene ved åpning og tilkobling.

Beregningen av et k- sentrum kan gjøre det mulig å partisjonere data . Avstandene representerer da likheter, som for k-middel .

Merknader og referanser

Den franske oversettelsen kommer fra oversettelsen av Nicolas Shabanel av (en) Vijay Vazirani , Approximation algoritmer , Springer Verlag , 2001 (da 2003), 380 s. ( ISBN 978-3-540-65367-7 ), se “ Tilnærmelsesalgoritmer: innholdsfortegnelse ” , på Nicolas Schabanels nettsted .
Samir Khuller og Yoram J. Sussmann, “ The Capacitated \ emph {K} -Center Problem ”, SIAM J. Discrete Math. , vol. 13 n o 3, 2000, s. 403-418
Dorit S Hochbaum, "Ulike forestillinger om tilnærminger: Bra, bedre, best og mer" , i tilnærmelsesalgoritmer for NP-harde problemer , PWS Publishing Co., 1996, s. 346-446
(in) Michael Garey og David S. Johnson , Computers and Intractability: A Guide to theory of NP-Completeness , WH Freeman,1979( ISBN 0-7167-1045-5 ).
(en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski og Gerhard Woeginger, “ Metrisk k-senter ” , om et kompendium av NP-optimaliseringsproblemer ,2000.
Teofilo F. Gonzalez , “ Clustering to minimize the maximum intercluster distance ”, Theoretical Computer Science , vol. 38, 1985, s. 293-306 ( DOI 10.1016 / 0304-3975 (85) 90224-5 )
(no) Sanjoy Dasgupta, “ Forelesning 1: Klynging i metriske rom ” , om University of California i San Diego ,2013
Jack Edmonds og Delbert Ray Fulkerson , “ Bottleneck extrema, ” Journal of Combinatorial Theory , vol. 8, n o 3, 1970, s. 299-306.
(en) Vijay Vazirani , tilnærmingsalgoritmer , Springer Verlag , 2001 (da 2003), 380 s. ( ISBN 978-3-540-65367-7 ) , kap. 5 ("k-center")
Se lysbildene 14-19 av Thomas Rothvoss, “ Approximation Algorithm ” ,2009.
Dorit S. Hochbaum og David B. Shmoys , “ En best mulig heuristikk for k- senterproblemet ”, Mathematics of Operations Research , vol. 10, n o to 1985, s. 180-184
Wen-Lian Hsu og George L. Nemhauser, “ Easy and hard bottleneck location problems ”, Discrete Applied Mathematics , Elsevier, vol. 1, n o 3, 1979, s. 209-215
David Eisenstat, Philip N. Klein og Claire Mathieu, “Approximating k- center in planar grafer” , i Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, 5. januar 7, 2014 , 2014, s. 617-627
David P. Williamson og David B. Shmoys, kap. 2.2 “K-center-problemet” , i The Design of Approximation Algorithms , Cambridge University Press

Eksterne linker

(no) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski og Gerhard Woeginger , “ Metric k-center ” , om et kompendium av NP-optimaliseringsproblemer ,2000.
(no) Sanjoy Dasgupta, “ Forelesning 1: Klynging i metriske rom ” , på University of California i San Diego ,2013