Metriskt k -centrum

Inom grafteori är det metriska $-$ centerproblemet k ett kombinatoriskt optimeringsproblem som studeras inom teoretisk datavetenskap . Med tanke på $n$ städer med specificerade avstånd vill man bygga $k$ lager i olika städer och minimera det maximala avståndet från en stad till ett lager. I grafteorin betyder detta att man hittar en uppsättning av $k$ hörn för vilka det största avståndet av någon punkt till dess närmaste vertex i $k$ -mängden är minimum. Topparna måste vara i ett metriskt utrymme , vilket ger en komplett graf som uppfyller triangelolikheten .

Formell definition

Låt $(X,d)$ vara ett metriskt utrymme där $X$ är en mängd och $d$ är en metrisk A-mängd $\mathbf { V} \subseteq {\mathcal {X}}$ , tillhandahålls tillsammans med en parameter $k$ . Målet är att hitta en delmängd ${\mathcal {C}}\subseteq \mathbf {V}$ med $|{\mathcal {C}}|=k$ så att det maximala avståndet för en punkt i $\mathbf {V}$ till den närmaste punkten i ${\mathcal {C }}$ minimeras. Problemet kan formellt definieras enligt följande: För ett metriskt utrymme ( ${\displaystyle {\mathcal {X}}} ,$ d),

Ingång: en uppsättning ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}} ,$ och en parameter $k$ .
Utdata: en uppsättning ${\mathcal {C}}\subseteq \mathbf {V}$ av $k$ punkter.
Mål: Minimera kostnaden $r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}$ d(v, ${\mathcal {C}}$ )

Det vill säga, varje punkt i ett kluster är högst i avstånd $r^{\mathcal {C}}(V)$ från dess respektive centrum.

K-Center Clustering-problemet kan också definieras på en fullständig oriktad graf G = ( V , E ) enligt följande: Givet en fullständig oriktad graf G = ( V , E ) med avstånden d ( v _i , v _j ) ∈ N uppfyller triangelolikheten, hitta en delmängd C ⊆ V med | C | = k medan du minimerar:

\max _{v\in V}\min _{c\in C}d(v,c)

Beräkningskomplexitet

I en fullständig oriktad graf G = ( V , E ), om vi sorterar kanterna i icke-minskande ordning av avstånden: d ( e ₁ ) ≤ d ( e ₂ ) ≤ … ≤ d ( e _m ) och låter G _i = (V, _Ei ) , _där Ei = { _ei , e2 _, …, _ei } . K - centerproblemet är ekvivalent med att hitta det minsta indexet i så att Gi har en dominerande uppsättning storlek som mest k _.

Även om Dominating Set är NP-komplett , förblir k -centerproblemet NP-hårt . Detta är tydligt, eftersom optimaliteten för en given genomförbar lösning för k -centerproblemet kan bestämmas genom Dominating Set-reduktionen endast om vi först vet storleken på den optimala lösningen (dvs. det minsta indexet i så att G _i har en dominerande uppsättning storlek högst k ), vilket är just den svåra kärnan i NP-Hard- problemen. Även om en Turing-reduktion kan komma runt detta problem genom att prova alla värden på k .

Uppskattningar

En enkel girig algoritm

En enkel girig approximationsalgoritm som uppnår en approximationsfaktor på 2 bygger ${\mathcal {C}}$ med hjälp av en längst-först genomgång i k iterationer. Denna algoritm väljer helt enkelt den punkt som ligger längst bort från den aktuella uppsättningen av centra i varje iteration som det nya centret. Det kan beskrivas på följande sätt:

Välj en godtycklig punkt ${\bar {c}}_{1}$ till $C_{1}$
För varje punkt $v\in \mathbf {V}$ beräkna $d_{1}[v]$ från ${\bar {c}}_ {1}$
Välj punkten ${\bar {c}}_{2}$ med högsta avstånd från ${\bar {c}}_{1}$ .
Lägg till den till uppsättningen av centra och beteckna denna utökade uppsättning centra som $C_{2}$ . Fortsätt detta tills k centra hittas

Körtid

Att välja det ^{i :}^te centret tar ${\mathcal {O}}(n)$ tid.
Det finns k sådana iterationer.
Således tar algoritmen totalt ${\mathcal {O}}(nk)$ tid.

Bevisa approximationsfaktorn

Lösningen som erhålls med den enkla giriga algoritmen är en 2-approximation till den optimala lösningen. Detta avsnitt fokuserar på att bevisa denna approximationsfaktor.

Givet en uppsättning av n punkter ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}} ,$ som tillhör ett metriskt utrymme ( ${\displaystyle {\mathcal {X}}} ,$ d), den giriga K -centeralgoritmen beräknar en uppsättning K av k centra, så att K är en 2-approximation till den optimala k -centerklustringen av V .

dvs $r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} , {\textit {k}})$

Denna sats kan bevisas med två fall enligt följande,

Fall 1: Varje kluster av ${\mathcal {C}}_{opt}$ innehåller exakt en punkt av $\mathbf {K}$

Betrakta en punkt $v\in \mathbf {V}$
Låt ${\bar {c}}$ vara mitten den tillhör i ${\mathcal {C}}_{opt}$
Låt ${\bar {k}}$ vara mitten av $\mathbf {K}$ som är i $\Pi ({\mathcal {C}}_{opt},{\bar {c}})$
$d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)$
På liknande sätt, $d({\bar {k}},{\bar {c}})=d( {\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}$
Genom triangelolikheten: $d(v,{\bar {k}}) \leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}$

Fall 2: Det finns två centra ${\bar {k}}$ och ${\bar {u}}$ av $\mathbf {K}$ som båda är i ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})} ,$ för vissa ${\displaystyle { \bar {c}}\in {\mathcal {C}}_{opt}} ($ enligt duvhålsprincipen är detta den enda andra möjligheten)

Antag, utan förlust av allmänhet, att ${\bar {u}}$ lades till senare till mittmängden $\mathbf {K}$ av den giriga algoritmen, säg i i: ^te iterationen.
Men eftersom den giriga algoritmen alltid väljer den punkt som är längst bort från den aktuella uppsättningen av centra, har vi att ${\bar {k}}\in {\mathcal {C}}_{i -1}$ och,

${\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1 }}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}}, {\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}}) \\&\leq 2r^{opt}\end{aligned}}$

Ytterligare en 2-faktors approximationsalgoritm

En annan algoritm med samma approximationsfaktor drar fördel av det faktum att k -Center-problemet är ekvivalent med _att hitta det minsta indexet i så att Gi har en dominerande uppsättning storlek som mest k och beräknar en maximal oberoende uppsättning av Gi _, för det minsta index i som har en maximal oberoende mängd med en storlek på minst k . Det är inte möjligt att hitta en approximationsalgoritm med en approximationsfaktor på 2 − ε för någon ε > 0, såvida inte P = NP. Vidare måste avstånden för alla kanter i G uppfylla triangelolikheten om k -centrumproblemet ska approximeras inom någon konstant faktor, om inte P = NP.

Parameteriserade approximationer

Det kan visas att k -Center-problemet är W[2]-svårt att approximera inom en faktor 2 − ε för någon ε > 0, när k används som parameter. Detta gäller även när man parametriserar med dubbleringsdimensionen (i själva verket dimensionen för ett Manhattan-mått ), såvida inte P=NP . När man betraktar den kombinerade parametern som ges av k och dubbleringsdimensionen , är k -Center fortfarande W[1]-hård men det är möjligt att få ett parameteriserat approximationsschema . Detta är till och med möjligt för varianten med vertexkapacitet, som begränsar hur många hörn som kan tilldelas ett öppet centrum av lösningen.

Se även

^ ^a ^b ^c Har-peled, Sariel (2011). Geometriska approximationsalgoritmer . Boston, MA, USA: American Mathematical Society. ISBN 0821849115 .
^ Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, s. 47–48, ISBN 3-540-65367-8
^ Gonzalez, Teofilo F. (1985), "Klustring för att minimera det maximala interklusteravståndet", Theoretical Computer Science , vol. 38, Elsevier Science BV, s. 293–306, doi : 10.1016/0304-3975(85)90224-5
^ Hochbaum, Dorit S. ; Shmoys, David B. (1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM , vol. 33, s. 533–550, ISSN 0004-5411
^ Hochbaum, Dorit S. (1997), Approximation Algorithms for NP-Hard problems , Boston: PWS Publishing Company, s. 346–398, ISBN 0-534-94968-1
^ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Minimum k-center", A Compendium of NP Optimization Problems
^ Feldmann, Andreas Emil (2019-03-01). "Approximationer med fasta parametrar för k-centerproblem i grafer med låga motorvägsdimensioner" . Algoritmik . 81 (3): 1031-1052. doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 .
^ Feder, Tomás; Greene, Daniel (1988-01-01). "Optimala algoritmer för ungefärlig klustring" . Handlingar från det tjugonde årliga ACM-symposiet om datorteori . STOC '88. New York, NY, USA: Association for Computing Machinery: 434–444. doi : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 .
^ Feldmann, Andreas Emil; Marx, Dániel (2020-07-01). "Den parametriserade hårdheten hos k-Center-problemet i transportnätverk" . Algoritmik . 82 (7): 1989–2005. doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 .
^ Feldmann, Andreas Emil; Vu, Tung Anh (2022). Bekos, Michael A.; Kaufmann, Michael (red.). "Generaliserat $$k$$-Center: Distinguishing Doubling and Highway Dimension" . Grafteoretiska begrepp i datavetenskap . Cham: Springer International Publishing: 215–229. doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

Vidare läsning

Hochbaum, Dorit S. ; Shmoys, David B. (1985), "A Best Possible Heuristic for the k-Center Problem", Mathematics of Operations Research , vol. 10, s. 180–184

[Har-peled:2011:GAA:2031416-1] Har-peled, Sariel (2011). Geometriska approximationsalgoritmer . Boston, MA, USA: American Mathematical Society. ISBN 0821849115 .

[2] Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, s. 47–48, ISBN 3-540-65367-8

[3] Gonzalez, Teofilo F. (1985), "Klustring för att minimera det maximala interklusteravståndet", Theoretical Computer Science , vol. 38, Elsevier Science BV, s. 293–306, doi : 10.1016/0304-3975(85)90224-5

[4] Hochbaum, Dorit S. ; Shmoys, David B. (1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM , vol. 33, s. 533–550, ISSN 0004-5411

[5] Hochbaum, Dorit S. (1997), Approximation Algorithms for NP-Hard problems , Boston: PWS Publishing Company, s. 346–398, ISBN 0-534-94968-1

[6] Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Minimum k-center", A Compendium of NP Optimization Problems

[7] Feldmann, Andreas Emil (2019-03-01). "Approximationer med fasta parametrar för k-centerproblem i grafer med låga motorvägsdimensioner" . Algoritmik . 81 (3): 1031-1052. doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 .

[8] Feder, Tomás; Greene, Daniel (1988-01-01). "Optimala algoritmer för ungefärlig klustring" . Handlingar från det tjugonde årliga ACM-symposiet om datorteori . STOC '88. New York, NY, USA: Association for Computing Machinery: 434–444. doi : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 .

[9] Feldmann, Andreas Emil; Marx, Dániel (2020-07-01). "Den parametriserade hårdheten hos k-Center-problemet i transportnätverk" . Algoritmik . 82 (7): 1989–2005. doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 .

[10] Feldmann, Andreas Emil; Vu, Tung Anh (2022). Bekos, Michael A.; Kaufmann, Michael (red.). "Generaliserat $$k$$-Center: Distinguishing Doubling and Highway Dimension" . Grafteoretiska begrepp i datavetenskap . Cham: Springer International Publishing: 215–229. doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .