Метрический k -центр

В теории графов задачу изучаемую $комбинаторной$ оптимизации проблема метрического k-центра представляет собой , в теоретической информатике . Учитывая $n$ городов с заданными расстояниями, нужно построить $k$ складов в разных городах и минимизировать максимальное расстояние города до склада. В теории графов это означает поиск набора из $k$ вершин , для которого наибольшее расстояние любой точки до ближайшей вершины в $k$ -множестве минимально. Вершины должны находиться в метрическом пространстве , образуя полный граф , удовлетворяющий неравенству треугольника .

Формальное определение

Позволять $(X,d)$ быть метрическим пространством , где $X$ представляет собой набор и $d$ это метрика
Набор $\mathbf {V} \subseteq {\mathcal {X}}$ , предоставляется вместе с параметром $k$ . Цель — найти подмножество ${\mathcal {C}}\subseteq \mathbf {V}$ с $|{\mathcal {C}}|=k$ такое, что максимальное расстояние до точки в $\mathbf {V}$ до ближайшей точки в ${\mathcal {C}}$ сведен к минимуму. Формально задачу можно определить следующим образом:
Для метрического пространства ( ${\mathcal {X}}$ ,г),

Вход : набор $\mathbf {V} \subseteq {\mathcal {X}}$ и параметр $k$ .
Выход : набор ${\mathcal {C}}\subseteq \mathbf {V}$ из $k$ точки.
Цель : минимизировать затраты. $r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}$ d(v, ${\mathcal {C}}$ )

То есть каждая точка в кластере находится на расстоянии не более $r^{\mathcal {C}}(V)$ из соответствующего центра. ^[1]

Задача кластеризации k-центров также может быть определена на полном неориентированном графе G = ( V , E ) следующим образом:
Учитывая полный неориентированный граф G = ( V , E ) с расстояниями d ( v _i , v _j ) ∈ N , удовлетворяющими неравенству треугольника, найдите подмножество C ⊆ V с | С | = k при минимизации:

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

Вычислительная сложность

В полном неориентированном графе G = ( V , E ), если мы отсортируем ребра в неубывающем порядке расстояний: d ( e ₁ ) ≤ d ( e ₂ ) ≤ ... ≤ d ( e _m ) и пусть G _i = (V, E _i ), где E _i знак равно { е ₁ , е ₂ , ..., е _i }. Проблема k -центра эквивалентна поиску наименьшего индекса i такого, что G _i имеет доминирующий набор размера не более k . ^[2]

Хотя доминирующее множество является NP-полным , проблема k -центра остается NP-трудной . Это ясно, поскольку оптимальность данного допустимого решения проблемы с k -центрами может быть определена посредством сокращения доминирующего множества только в том случае, если мы в первую очередь знаем размер оптимального решения (т. е. наименьший индекс i такой, что G _i имеет размером доминирующий набор не более k ), что и составляет суть сложных задач NP-Hard . Хотя сокращение Тьюринга может обойти эту проблему, перепробовав все значения k .

Приближения

Простой жадный алгоритм

Простой жадный алгоритм аппроксимации , обеспечивающий коэффициент аппроксимации 2. ${\mathcal {C}}$ используя самый дальний обход за k итераций. Этот алгоритм просто выбирает точку, наиболее удаленную от текущего набора центров на каждой итерации, в качестве нового центра. Его можно описать следующим образом:

Выберите произвольную точку ${\bar {c}}_{1}$ в $C_{1}$
Для каждой точки $v\in \mathbf {V}$ вычислить $d_{1}[v]$ от ${\bar {c}}_{1}$
Выберите точку ${\bar {c}}_{2}$ с наибольшим расстоянием от ${\bar {c}}_{1}$ .
Добавим его к множеству центров и обозначим это расширенное множество центров как $C_{2}$ . Продолжайте до тех пор, пока не будет найдено k центров.

Время работы

Я ^й итерация выбора i ^й центр берет ${\mathcal {O}}(n)$ время.
Таких итераций k .
Таким образом, в целом алгоритм занимает ${\mathcal {O}}(nk)$ время. ^[3]

Доказательство коэффициента аппроксимации

Решение, полученное с помощью простого жадного алгоритма, представляет собой 2-приближение оптимального решения. В этом разделе основное внимание уделяется доказательству этого коэффициента аппроксимации.

Дан набор из n точек $\mathbf {V} \subseteq {\mathcal {X}}$ , принадлежащий метрическому пространству ( ${\mathcal {X}}$ ,d), жадный алгоритм K -центров вычисляет набор K из k- центров, такой, что K является 2-аппроксимацией оптимальной k кластеризации -центров V .

то есть $r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})$ ^[1]

Эту теорему можно доказать, используя следующие два случая:

Случай 1: Каждый кластер ${\mathcal {C}}_{opt}$ содержит ровно одну точку $\mathbf {K}$

Рассмотрим точку $v\in \mathbf {V}$
Позволять ${\bar {c}}$ быть центром, которому он принадлежит в ${\mathcal {C}}_{opt}$
Позволять ${\bar {k}}$ быть центром $\mathbf {K}$ это в $\Pi ({\mathcal {C}}_{opt},{\bar {c}})$
$d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)$
Сходным образом, $d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}$
По неравенству треугольника: $d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}$

Случай 2: Есть два центра ${\bar {k}}$ и ${\bar {u}}$ из $\mathbf {K}$ которые оба в $\Pi ({\mathcal {C}}_{opt},{\bar {c}})$ , для некоторых ${\bar {c}}\in {\mathcal {C}}_{opt}$ (По принципу ячейки это единственная другая возможность)

Предположим, не ограничивая общности, что ${\bar {u}}$ был добавлен позже в центральный набор $\mathbf {K}$ по жадному алгоритму, скажем, в i ^й итерация.
Но поскольку жадный алгоритм всегда выбирает точку, наиболее удаленную от текущего набора центров, мы имеем следующее: ${\bar {k}}\in {\mathcal {C}}_{i-1}$ и,

${\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}}$ ^[1]

Еще один алгоритм двухфакторной аппроксимации

Другой алгоритм с тем же коэффициентом аппроксимации использует тот факт, что проблема k -центра эквивалентна поиску наименьшего индекса i такого, что G _i имеет доминирующий набор размера не более k, и вычисляет максимальный независимый набор Gi _, выглядя для наименьшего индекса i , который имеет максимальное независимое множество размером не менее k . ^[4]Невозможно найти алгоритм аппроксимации с коэффициентом аппроксимации 2 − ε для любого ε > 0, если только P = NP. ^[5]Более того, расстояния всех ребер в G должны удовлетворять неравенству треугольника, если задача k -центра должна быть аппроксимирована с любым постоянным коэффициентом, если только P = NP. ^[6]

Параметризованные аппроксимации

Можно показать, что проблему k -центра W[2]-трудно аппроксимировать с точностью до коэффициента 2 - ε для любого ε > 0 при использовании k в качестве параметра. ^[7] Это также верно при параметризации с помощью удвоенного измерения (фактически, измерения манхэттенской метрики ), если только P=NP . ^[8] При рассмотрении комбинированного параметра, заданного k , и удвоенной размерности , k -Center по-прежнему W[1]-труден, но можно получить параметризованную схему аппроксимации . ^[9] Это возможно даже для варианта с емкостью вершин, которая ограничивает количество вершин, которые можно отнести к открытому центру решения. ^[10]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Хар-пелед, Сариэль (2011). Алгоритмы геометрической аппроксимации . Бостон, Массачусетс, США: Американское математическое общество. ISBN 978-0821849118 .
^ Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, pp. 47–48, ISBN 3-540-65367-8
^ Гонсалес, Теофило Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , vol. 38, Elsevier Science BV, стр. 293–306, номер документа : 10.1016/0304-3975(85)90224-5.
^ Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1986), «Единый подход к алгоритмам аппроксимации проблем с узкими местами», Journal of the ACM , vol. 33, стр. 533–550, doi : 10.1145/5925.5933 , ISSN 0004-5411 , S2CID 17975253
^ Хохбаум, Дорит С. (1997), Алгоритмы аппроксимации для NP-сложных задач , Бостон: PWS Publishing Company, стр. 346–398, ISBN 0-534-94968-1
^ Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Воегингер, Герхард (2000), «Минимальный k-центр», Сборник задач оптимизации NP
^ Фельдманн, Андреас Эмиль (01 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах малых размеров шоссе» (PDF) . Алгоритмика . 81 (3): 1031–1052. дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .
^ Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .
^ Фельдманн, Андреас Эмиль; Маркс, Даниэль (01 июля 2020 г.). «Параметризованная жесткость проблемы k-центра в транспортных сетях» (PDF) . Алгоритмика . 82 (7): 1989–2005. дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .
^ Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различие удвоения и измерения шоссе» . В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

Дальнейшее чтение

Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1985), «Наилучшая возможная эвристика для проблемы k-центра», Mathematics of Operations Research , vol. 10, стр. 180–184, doi : 10.1287/мор.10.2.180

[Har-peled:2011:GAA:2031416-1] Перейти обратно: ^а ^б ^с Хар-пелед, Сариэль (2011). Алгоритмы геометрической аппроксимации . Бостон, Массачусетс, США: Американское математическое общество. ISBN 978-0821849118 .

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

[3] Гонсалес, Теофило Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , vol. 38, Elsevier Science BV, стр. 293–306, номер документа : 10.1016/0304-3975(85)90224-5.

[4] Хохбаум, Дорит С .; Шмойс, Дэвид Б. (1986), «Единый подход к алгоритмам аппроксимации проблем с узкими местами», Journal of the ACM , vol. 33, стр. 533–550, doi : 10.1145/5925.5933 , ISSN 0004-5411 , S2CID 17975253

[5] Хохбаум, Дорит С. (1997), Алгоритмы аппроксимации для NP-сложных задач , Бостон: PWS Publishing Company, стр. 346–398, ISBN 0-534-94968-1

[6] Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Воегингер, Герхард (2000), «Минимальный k-центр», Сборник задач оптимизации NP

[7] Фельдманн, Андреас Эмиль (01 марта 2019 г.). «Аппроксимации с фиксированными параметрами для задач k-центра в графах малых размеров шоссе» (PDF) . Алгоритмика . 81 (3): 1031–1052. дои : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .

[8] Федер, Томас; Грин, Дэниел (1 января 1988 г.). «Оптимальные алгоритмы приближенной кластеризации» . Материалы двадцатого ежегодного симпозиума ACM по теории вычислений - STOC '88 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 434–444. дои : 10.1145/62212.62255 . ISBN 978-0-89791-264-8 . S2CID 658151 .

[9] Фельдманн, Андреас Эмиль; Маркс, Даниэль (01 июля 2020 г.). «Параметризованная жесткость проблемы k-центра в транспортных сетях» (PDF) . Алгоритмика . 82 (7): 1989–2005. дои : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .

[10] Фельдманн, Андреас Эмиль; Ву, Тунг Ань (2022). «Обобщенный $$k$$-центр: различие удвоения и измерения шоссе» . В Бекосе, Майкл А.; Кауфманн, Майкл (ред.). Теоретико-графовые концепции в информатике . Конспекты лекций по информатике. Том. 13453. Чам: Springer International Publishing. стр. 215–229. arXiv : 2209.00675 . дои : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]