Metrický K-střed - Metric k-center

v teorie grafů, metrický k-centrum nebo umístění metrického zařízení problém je kombinatorická optimalizace problém studoval v teoretická informatika. Dáno n města se specifikovanými vzdálenostmi chce člověk stavět k sklady v různých městech a minimalizovat maximální vzdálenost města od skladu. V teorii grafů to znamená nalezení množiny k vrcholy, pro které je největší vzdálenost kteréhokoli bodu k jeho nejbližšímu vrcholu v k-set je minimum. Vrcholy musí být v metrickém prostoru, za předpokladu, že kompletní graf který uspokojuje nerovnost trojúhelníku.

Formální definice

Nechat ${ displaystyle (X, d)}$ být metrický prostor kde ${ displaystyle X}$ je sada a ${ displaystyle d}$ je metrický
Sada ${ displaystyle mathbf {V} subseteq { mathcal {X}}}$ , je poskytován společně s parametrem ${ displaystyle k}$ . Cílem je najít podmnožinu ${ displaystyle { mathcal {C}} subseteq mathbf {V}}$ s ${ displaystyle | { mathcal {C}} | = k}$ tak, aby maximální vzdálenost bodu v ${ displaystyle mathbf {V}}$ do nejbližšího bodu v ${ displaystyle { mathcal {C}}}$ je minimalizován. Problém lze formálně definovat takto:
Pro metrický prostor ( ${ displaystyle { mathcal {X}}}$ , d),

Vstup: sada ${ displaystyle mathbf {V} subseteq { mathcal {X}}}$ a parametr ${ displaystyle k}$ .
Výstup: sada ${ displaystyle { mathcal {C}}}$ z ${ displaystyle k}$ bodů.
Cíl: Minimalizovat náklady ${ displaystyle r ^ { mathcal {C}} ( mathbf {V}) = { podmnožina {v ve V} { max}}}$ d (v, ${ displaystyle { mathcal {C}}}$ )

To znamená, že každý bod v klastru je nanejvýš ve vzdálenosti ${ displaystyle r ^ { mathcal {C}} (V)}$ z příslušného středu. ^[1]

Problém k-Center Clustering lze definovat také na úplném neorientovaném grafu G = (PROTI, E) jak následuje:
Vzhledem k úplnému neorientovanému grafu G = (PROTI, E) se vzdálenostmi d(proti_i, proti_j) ∈ N uspokojení nerovnosti trojúhelníku, najděte podmnožinu C ⊆ PROTI s |C| = k při minimalizaci:

{ displaystyle max _ {v ve V} min _ {c v C} d (v, c)}

Výpočetní složitost

V úplném neorientovaném grafu G = (PROTI, E), pokud seřadíme hrany v neklesajícím pořadí vzdáleností: d(E₁) ≤ d(E₂) ≤ … ≤ d(E_m) a nechte G_i = (V,E_i), kde E_i = {E₁, E₂, …, E_i}. The k-center problém je ekvivalentní nalezení nejmenšího indexu i takhle G_i má dominující sada maximálně velikosti k.^[2]

Ačkoli dominující sada je NP-kompletní, k-středový problém přetrvává NP-tvrdé. To je jasné, protože optimálnost daného proveditelného řešení pro k-středový problém lze určit pomocí redukce Dominující sady pouze v případě, že víme na prvním místě velikost optimálního řešení (tj. nejmenší index i takhle G_i má dominující sada maximálně velikosti k), což je přesně obtížné jádro NP-tvrdý problémy.

Aproximace

Jednoduchý chamtivý algoritmus

Jednoduchý chamtivý aproximační algoritmus který dosahuje aproximačního faktoru 2 sestavení ${ displaystyle { mathcal {C}}}$ používat nejdále první průchod v k iterace. Tento algoritmus jednoduše vybere bod nejvzdálenější od aktuální sady středů v každé iteraci jako nový střed. Lze to popsat takto:

Vyberte libovolný bod ${ displaystyle { bar {c}} _ {1}}$ do ${ displaystyle C_ {1}}$
Za každý bod ${ displaystyle v in mathbf {V}}$ vypočítat ${ displaystyle d_ {1} [v]}$ z ${ displaystyle { bar {c}} _ {1}}$
Vyberte si bod ${ displaystyle { bar {c}} _ {2}}$ s nejvyšší vzdáleností od ${ displaystyle { bar {c}} _ {1}}$ .
Přidejte jej do sady center a označte tuto rozšířenou sadu center jako ${ displaystyle C_ {2}}$ . Pokračujte až do k centra jsou nalezena

Provozní doba

I^th iterace výběru i^th centrum trvá ${ displaystyle { mathcal {O}} (n)}$ čas.
Existují k takové iterace.
Algoritmus tedy celkově trvá ${ displaystyle { mathcal {O}} (nk)}$ čas.^[3]

Prokázání aproximačního faktoru

Řešení získané pomocí jednoduchého chamtivého algoritmu je 2-aproximace optimálního řešení. Tato část se zaměřuje na prokázání tohoto přibližného faktoru.

Vzhledem k souboru n bodů ${ displaystyle mathbf {V} subseteq { mathcal {X}}}$ , patřící do metrického prostoru ( ${ displaystyle { mathcal {X}}}$ , d), chamtivý K.-centrický algoritmus vypočítá množinu K. z k centra, taková K. je 2-přiblížení k optimálnímu k-centrování shluků PROTI.

tj. ${ displaystyle r ^ { mathbf {K}} ( mathbf {V}) leq 2r ^ {opt} ( mathbf {V}, { textit {k}})}$ ^[1]

Tuto větu lze dokázat pomocí dvou následujících případů,

Případ 1: Každý shluk ${ displaystyle { mathcal {C}} _ {opt}}$ obsahuje přesně jeden bod ${ displaystyle mathbf {K}}$

Zvažte bod ${ displaystyle v in mathbf {V}}$
Nechat ${ displaystyle { bar {c}}}$ být centrem, kam patří ${ displaystyle { mathcal {C}} _ {opt}}$
Nechat ${ displaystyle { bar {k}}}$ být centrem ${ displaystyle mathbf {K}}$ to je v ${ displaystyle Pi ({ mathcal {C}} _ {opt}, { bar {c}})}$
${ displaystyle d (v, { bar {c}}) = d (v, { mathcal {C}} _ {opt}) leq r ^ {opt} ( mathbf {V}, k)}$
Podobně, ${ displaystyle d ({ bar {k}}, { bar {c}}) = d ({ bar {k}}, { mathcal {C}} _ {opt}) leq r ^ {opt }}$
Podle nerovnosti trojúhelníku: ${ displaystyle d (v, { bar {k}}) leq d (v, { bar {c}}) + d ({ bar {c}}, { bar {k}}) leq 2r ^ {opt}}$

Případ 2: Existují dvě centra ${ displaystyle { bar {k}}}$ a ${ displaystyle { bar {u}}}$ z ${ displaystyle mathbf {K}}$ které jsou oba uvnitř ${ displaystyle Pi ({ mathcal {C}} _ {opt}, { bar {c}})}$ , pro některé ${ displaystyle { bar {c}} in { mathcal {C}} _ {opt}}$ (Podle principu holubí díry je to jediná další možnost)

Předpokládejme to, aniž bychom ztratili obecnost ${ displaystyle { bar {u}}}$ byl přidán později do středové sady ${ displaystyle mathbf {K}}$ chamtivým algoritmem, řekněme v i^th opakování.
Ale protože chamtivý algoritmus vždy vybírá bod nejdále od aktuální sady center, máme to ${ displaystyle { bar {k}} v { mathcal {C}} _ {i-1}}$ a,

${ displaystyle { 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 {zarovnáno}}}$ ^[1]

Další dvoufaktorový aproximační algoritmus

Další algoritmus se stejným aproximačním faktorem využívá skutečnosti, že k-center problém je ekvivalentní nalezení nejmenšího indexu i takhle G_i má nejvýše dominující množinu k a vypočítá maximum nezávislá sada z G_i, hledající nejmenší index i který má maximální nezávislou množinu o velikosti alespoň k.^[4]Pro žádné ε> 0 není možné najít aproximační algoritmus s aproximačním faktorem 2 - ε, pokud P = NP.^[5]Dále vzdálenosti všech hran v G musí splňovat nerovnost trojúhelníku, pokud k-středový problém má být aproximován v rámci libovolného konstantního faktoru, pokud P = NP.^[6]

Viz také

Reference

^ ^A ^b ^C Har-peled, Sariel (2011). Algoritmy geometrické aproximace. Boston, MA, USA: Americká matematická společnost. ISBN 0821849115.
^ Vazirani, Vijay V. (2003), Aproximační algoritmy, Berlín: Springer, s. 47–48, ISBN 3-540-65367-8
^ Gonzalez, Teofilo F. (1985), „Shlukování, aby se minimalizovala maximální vzdálenost mezi klastry“, Teoretická informatika, 38, Elsevier Science B.V., str. 293–306, doi:10.1016/0304-3975(85)90224-5
^ Hochbaum, Dorit S.; Shmoys, David B. (1986), „Jednotný přístup k aproximačním algoritmům pro problémy s úzkým hrdlem“, Deník ACM, 33, str. 533–550, ISSN 0004-5411
^ Hochbaum, Dorit S. (1997), Aproximační algoritmy pro NP-Hard problémy, 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“, Kompendium problémů s optimalizací NP

Další čtení

Hochbaum, Dorit S.; Shmoys, David B. (1985), „Nejlepší možná heuristika pro problém k-centra“, Matematika operačního výzkumu, 10, s. 180–184

[Har-peled:2011:GAA:2031416-1] A ^b ^C Har-peled, Sariel (2011). Algoritmy geometrické aproximace. Boston, MA, USA: Americká matematická společnost. ISBN 0821849115.

[2] Vazirani, Vijay V. (2003), Aproximační algoritmy, Berlín: Springer, s. 47–48, ISBN 3-540-65367-8

[3] Gonzalez, Teofilo F. (1985), „Shlukování, aby se minimalizovala maximální vzdálenost mezi klastry“, Teoretická informatika, 38, Elsevier Science B.V., str. 293–306, doi:10.1016/0304-3975(85)90224-5

[4] Hochbaum, Dorit S.; Shmoys, David B. (1986), „Jednotný přístup k aproximačním algoritmům pro problémy s úzkým hrdlem“, Deník ACM, 33, str. 533–550, ISSN 0004-5411

[5] Hochbaum, Dorit S. (1997), Aproximační algoritmy pro NP-Hard problémy, 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“, Kompendium problémů s optimalizací NP

[1]

[2]

[3]

[4]

[5]

[6]