Centrum k metryczne

W teorii grafów metryczny $k$ -centrum problem jest kombinatorycznym problemem optymalizacyjnym badanym w informatyce teoretycznej . Biorąc pod uwagę $n$ miast o określonych odległościach, chcemy zbudować $k$ magazynów w różnych miastach i zminimalizować maksymalną odległość miasta od magazynu. W teorii grafów oznacza to znalezienie zbioru $k$ wierzchołków , dla których największa odległość dowolnego punktu do jego najbliższego wierzchołka w $k$ -zestaw jest minimalny. Wierzchołki muszą znajdować się w przestrzeni metrycznej , tworząc pełny wykres spełniający nierówność trójkąta .

Definicja formalna

Niech ${\ Displaystyle (X, d)}$ będzie przestrzenią metryczną , w której ${\ Displaystyle \ mathbf { V} \subseteq {\ mathcal {X}}}$ zbiorem, a $d}$ $Displaystyle$ jest metryką ZA zestaw jest dostarczany wraz z parametrem ${\ displaystyle k}$ . Celem jest znalezienie podzbioru $subseteq \ mathbf {V}}$
z ${\ Displaystyle | {\ mathcal {C}}|= k}$ tak, że maksymalna odległość punktu w ${\ Displaystyle \ mathbf {V}}$ do najbliższego punktu w do ${\ displaystyle {\ mathcal {C$ jest zminimalizowane. Problem można formalnie zdefiniować w następujący sposób: dla przestrzeni metrycznej ( d ), ${\ displaystyle {\ mathcal {X}}}$

$\$ $k}$ : zestaw i parametr .
$.$ : zbiór punktów do $}$
Cel: zminimalizować koszt ${\ Displaystyle r ^ {\ mathcal {C}} (\ mathbf {V}) = {\ underset {v \ in V} {\ max}}}$ re (v, ${\ Displaystyle {\ mathcal {C}}}$ )

$że$ każdy punkt w klastrze znajduje się co najwyżej w odległości .

K-Center Clustering problem można również zdefiniować na kompletnym grafie nieskierowanym G = ( V , E ) w następujący sposób: Dany kompletny graf nieskierowany G = ( V , E ) z odległościami d ( v _i , v _j ) ∈ N spełnia nierówność trójkąta, znajdź podzbiór C ⊆ V z | C | = k podczas minimalizacji:

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

Złożoność obliczeniowa

W pełnym grafie nieskierowanym G = ( V , E ), jeśli posortujemy krawędzie _w niemalejącym porządku odległości: d ( e ₁ ) ≤ d ( e ₂ ) ≤ … ≤ d ( em ) i niech G _i = (V, mi _ja ), gdzie mi _ja = { mi ₁ , mi ₂ , …, mi _ja }. k _ Problem -centrum jest równoważny znalezieniu najmniejszego indeksu i takiego, że G _i ma dominujący zbiór rozmiarów co najwyżej k .

Chociaż zbiór dominujący jest NP-zupełny , problem k -centrum pozostaje NP-trudny . Jest to jasne, ponieważ optymalność danego możliwego rozwiązania problemu k -centrum można określić za pomocą redukcji zbioru dominującego tylko wtedy, gdy znamy na pierwszym miejscu rozmiar rozwiązania optymalnego (tj. najmniejszy indeks i taki, że G _i ma dominującym zbiorem wielkości co najwyżej k ), co jest właśnie trudnym rdzeniem problemów NP-trudnych . Chociaż Redukcja Turinga może obejść ten problem, wypróbowując wszystkie wartości k .

przybliżenia

Prosty algorytm zachłanny

Prosty algorytm zachłannej aproksymacji , który osiąga współczynnik aproksymacji równy 2, buduje $użyciu$ najdalszego pierwszego przejścia w k iteracjach. Ten algorytm po prostu wybiera punkt najbardziej oddalony od bieżącego zestawu centrów w każdej iteracji jako nowe centrum. Można to opisać następująco:

Wybierz dowolny punkt ${\ Displaystyle {\ bar {c}} _ {1}}$ do do $Displaystyle C_ {1}}$
dla każdego punktu $\ w \ mathbf {V}}$ ${\ Displaystyle {\ bar {c}} _ {1}}$ oblicz ${\ Displaystyle d_ {1} [v]}$ od do
Wybierz punkt o największej odległości od $\ bar {c}} _ {1}$ $\ Displaystyle$ .
${\ displaystyle C_ {2}}$ do zestawu centrów i oznacz ten rozszerzony zestaw centrów jako do . Kontynuuj to, aż znajdziesz k centrów

Czas działania

I- $-$ ^iteracja wyboru ^tego centrum zajmuje
Jest k takich iteracji.
$_$ algorytm _

Dowód współczynnika przybliżenia

Rozwiązanie otrzymane za pomocą prostego algorytmu zachłannego jest przybliżeniem 2 do rozwiązania optymalnego. Ta sekcja koncentruje się na udowodnieniu tego współczynnika przybliżenia.

Biorąc pod uwagę zbiór n punktów należących do przestrzeni metrycznej ( , d) , ${\ Displaystyle \ mathbf {V} \ subseteq {\$ ${X}}}$ zachłanny algorytm K -center oblicza zbiór K z k centrów, tak że K jest przybliżeniem 2 do optymalnego skupienia k -center V .

tj. ${\ Displaystyle r ^ {\ mathbf {K}} (\ mathbf {V}) \ równoważnik 2r ^ {opt} (\ mathbf {V}, {\textit {k}})}$

Twierdzenie to można udowodnić za pomocą dwóch przypadków w następujący sposób,

Przypadek 1: Każdy klaster zawiera dokładnie jeden punkt $C}} _ {opt}$ $Displaystyle {\ mathcal {$

Rozważmy punkt ${\ Displaystyle v \ w \ mathbf {V}}$
Niech do $\ Displaystyle {\ bar {c}}}$ będzie centrum, do którego należy w do ${\ mathcal {C}} _ {opt}}$
Niech będzie środkiem ${\ Displaystyle$ $\ mathbf {K}}$ , czyli w $\ Displaystyle \ Pi ({$
${\ Displaystyle d (v, {\ bar {c}}) = d (v, {\ mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
Podobnie ${\ Displaystyle d ({\ bar {k}}, {\ bar {c}}) = d ( {\bar {k}},{\mathcal {C}}_ {opt})\leq r^{opt}}$
Z nierówności trójkąta: ${\ Displaystyle d (v, {\ bar {k}}) \leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

$oba$ 2 Istnieją $_$ $.$ i są $\ Displaystyle \ Pi ({\ mathcal {C}} _ {opt}, {\ bar {c}})}$ dla niektórych ${\ Displaystyle { \bar {c}}\w {\mathcal {C}}_{opt}}$ (Zgodnie z zasadą przegródki, jest to jedyna inna możliwość)

Załóżmy, bez utraty ogólności, że $przez$ później dodany do zbioru centralnego zachłanny algorytm, powiedzmy w $i$ ^tej .
Ale ponieważ zachłanny algorytm zawsze wybiera punkt najbardziej oddalony od bieżącego zestawu środków, mamy to $\ Displaystyle {\ bar {k}} \ in {\ mathcal {C}} _ {i -1}}$ i,

${\ Displaystyle {\ rozpocząć {wyrównane} r ^ {\ mathbf {K}} (\ mathbf {V}) \ równoważnik r ^ {{\ mathcal {C}} _ {i-1}} ( \mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\równoważnik d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\& \leq 2r^{opt}\end{wyrównane}}}$

Kolejny algorytm aproksymacji 2-czynnikowej

Inny algorytm z tym samym współczynnikiem przybliżenia wykorzystuje fakt, że problem k -Center jest równoważny znalezieniu najmniejszego indeksu i takiego, że G _i ma dominujący zbiór wielkości co najwyżej k i oblicza maksymalny niezależny zbiór Gi _, patrząc dla najmniejszego indeksu i , który ma maksymalny niezależny zbiór o rozmiarze co najmniej k . Nie jest możliwe znalezienie algorytmu aproksymacji ze współczynnikiem aproksymacji 2 - ε dla dowolnego ε > 0, chyba że P = NP. Ponadto odległości wszystkich krawędzi w G muszą spełniać nierówność trójkąta, jeśli k ma być aproksymowany w dowolnym stałym współczynniku, chyba że P = NP.

Sparametryzowane przybliżenia

Można pokazać, że problem k -Center jest W[2]-trudny do aproksymacji w ramach współczynnika 2 - ε dla dowolnego ε > 0, gdy używamy k jako parametru. Dotyczy to również parametryzacji według wymiaru podwojenia (w rzeczywistości wymiaru metryki Manhattanu ), chyba że P=NP . Biorąc pod uwagę połączony parametr określony przez k i wymiar podwojenia , k -Center jest nadal W[1]-twarde, ale możliwe jest uzyskanie sparametryzowanego schematu aproksymacji . Jest to nawet możliwe dla wariantu z pojemnościami wierzchołków, które określają, ile wierzchołków można przypisać do otwartego środka rozwiązania.

Zobacz też

^ ^a ^b ^c Har-peled, Sariel (2011). Algorytmy aproksymacji geometrycznej . Boston, MA, USA: Amerykańskie Towarzystwo Matematyczne. ISBN 0821849115 .
^ Vazirani, Vijay V. (2003), Algorytmy aproksymacji , Berlin: Springer, s. 47–48, ISBN 3-540-65367-8
^ Gonzalez, Teofilo F. (1985), „Klastrowanie w celu zminimalizowania maksymalnej odległości między klastrami”, Theoretical Computer Science , tom. 38, Elsevier Science BV, s. 293–306, doi : 10.1016/0304-3975(85)90224-5
^ Hochbaum Dorit S .; Shmoys, David B. (1986), „Ujednolicone podejście do algorytmów aproksymacji dla problemów wąskich gardeł”, Journal of the ACM , tom. 33, s. 533–550, ISSN 0004-5411
^ Hochbaum, Dorit S. (1997), Algorytmy aproksymacji dla problemów NP-trudnych , Boston: PWS Publishing Company, s. 346–398, ISBN 0-534-94968-1
^ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnus; Karpiński, Marek ; Woeginger, Gerhard (2000), „Minimalne centrum k”, Kompendium problemów optymalizacji NP
^ Feldmann, Andreas Emil (2019-03-01). „Aproksymacje ze stałymi parametrami dla problemów k-Center na wykresach wymiarów autostrad o niskim poziomie” . Algorytmika . 81 (3): 1031–1052. doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 .
^ Feder, Tomás; Greene, Daniel (1988-01-01). „Optymalne algorytmy dla przybliżonego grupowania” . Materiały z dwudziestego dorocznego sympozjum ACM poświęconego teorii obliczeń . STOK '88. Nowy Jork, NY, USA: Association for Computing Machinery: 434–444. doi : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 .
^ Feldmann, Andreas Emil; Marks, Daniel (2020-07-01). „Sparametryzowana twardość problemu k-centrum w sieciach transportowych” . Algorytmika . 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.). „Uogólnione centrum $$k$$: rozróżnianie podwojenia i wymiaru autostrady” . Graf-teoretyczne koncepcje w informatyce . Cham: Springer International Publishing: 215–229. doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

Dalsza lektura

Hochbaum, Dorit S .; Shmoys, David B. (1985), „Najlepsza możliwa heurystyka dla problemu k-Center”, Mathematics of Operations Research , tom. 10, s. 180–184

[Har-peled:2011:GAA:2031416-1] Har-peled, Sariel (2011). Algorytmy aproksymacji geometrycznej . Boston, MA, USA: Amerykańskie Towarzystwo Matematyczne. ISBN 0821849115 .

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

[3] Gonzalez, Teofilo F. (1985), „Klastrowanie w celu zminimalizowania maksymalnej odległości między klastrami”, Theoretical Computer Science , tom. 38, Elsevier Science BV, s. 293–306, doi : 10.1016/0304-3975(85)90224-5

[4] Hochbaum Dorit S .; Shmoys, David B. (1986), „Ujednolicone podejście do algorytmów aproksymacji dla problemów wąskich gardeł”, Journal of the ACM , tom. 33, s. 533–550, ISSN 0004-5411

[5] Hochbaum, Dorit S. (1997), Algorytmy aproksymacji dla problemów NP-trudnych , Boston: PWS Publishing Company, s. 346–398, ISBN 0-534-94968-1

[6] Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnus; Karpiński, Marek ; Woeginger, Gerhard (2000), „Minimalne centrum k”, Kompendium problemów optymalizacji NP

[7] Feldmann, Andreas Emil (2019-03-01). „Aproksymacje ze stałymi parametrami dla problemów k-Center na wykresach wymiarów autostrad o niskim poziomie” . Algorytmika . 81 (3): 1031–1052. doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 .

[8] Feder, Tomás; Greene, Daniel (1988-01-01). „Optymalne algorytmy dla przybliżonego grupowania” . Materiały z dwudziestego dorocznego sympozjum ACM poświęconego teorii obliczeń . STOK '88. Nowy Jork, NY, USA: Association for Computing Machinery: 434–444. doi : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 .

[9] Feldmann, Andreas Emil; Marks, Daniel (2020-07-01). „Sparametryzowana twardość problemu k-centrum w sieciach transportowych” . Algorytmika . 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.). „Uogólnione centrum $$k$$: rozróżnianie podwojenia i wymiaru autostrady” . Graf-teoretyczne koncepcje w informatyce . Cham: Springer International Publishing: 215–229. doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .