Задача о \(k\)-центрах

Рассмотрим следующую задачу. В сельском районе расположено несколько небольших населенных пунктов, связанных дорогами. Необходимо построить \(k\) больниц так, чтобы минимизировать максимальное расстояние от каждого населенного пункта до ближайшей больницы. Назовем эту задачу задачей о \(k\)-центрах. Далее в главе рассматривается задача о \(k\)-центрах и ее взвешенная версия при условии, что расстояния между городами удовлетворяют неравенству треугольника. Без такого ограничения для задачи о \(k\)-центрах не существует \(\alpha (n)\)-приближенных алгоритмов для любой полиномиально вычислимой функции \(\alpha (n)\) при условии, что \(P \neq N P\).

Пусть даны произвольное подмножество вершин \(S \subseteq V\) и произвольная вершина \(v \in V\). Определим расстояние от \(v\) до \(S\) как

\[ \operatorname {connect}(v, S) := \min \{ \operatorname {cost}(u, v) \mid u \in S\} \]

Метрическая задача о \(k\)-центрах

\(I = \left(G, \operatorname {cost}, k\right)\), где

• Полный граф \(G=(V, E)\);

• Стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\) такие, что для любых трех вершин \(u, v\) и \(w\) выполняется

  \[ \operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v) \]

• Натуральное число \(k \in \mathbb {N}\) (\(k \leq \left|V\right|\)), устанавливающее размер \(S\).

Найти подмножество вершин \(S \subseteq V\), с \(|S|=k\), которое минимизирует величину \[ \max _{v \in V} \left\{ \operatorname {connect}(v,S)\right\} \]

Метрическая задача о \(k\) центрах: пример

Полный граф на \(17\) вершинах, \(k=3\) (для наглядности показана часть рёбер). Наведите курсор на вершину — увидите, к какому центру она приписана.

1 Параметрическое сокращение для метрической задачи о \(k\)-центрах

Зачастую знание стоимости оптимального решения упрощает поиск хорошего приближенного решения. В частности, это позволяет отсечь заведомо неподходящие входные данные и сузить область поиска. К сожалению, вычисление стоимости оптимального решения имеет ту же сложность, что и нахождение самого решения NP-трудной оптимизационной задачи. Техника параметрического сокращения позволяет обходить эту трудность для некоторых задач. Выберем параметр \(t\), который является предположением о стоимости оптимального решения. Для выбранного значения \(t\) из заданного примера \(I\) удалим те данные, которые не будут использоваться в любом решении стоимостью не больше \(t\). Обозначим такой сокращенный пример как \(I(t)\).

Алгоритм состоит из нескольких идей. Пусть дана индивидуальная задача \(I\).

• Параметризация. Получить параметризованную задачу разрешимости (т.е. задачу с ответом “ДА”/“НЕТ”) \(\operatorname {decision}(I, t)\) для исходной задачи оптимизации:

  • \(\operatorname {optimization}(I)\): минимизировать (максимизировать) стоимость решения;

  • \(\operatorname {decision}(I, t)\): понять, есть ли допустимое решение стоимости \(\operatorname {cost} \leq t\) (\(\operatorname {cost} \geq t\)).

  Свести оптимизационную задачу к задаче разрешимости \(\operatorname {decision}(t)\): решать \(\operatorname {decision}(t)\) для возрастающих \(t\) до тех пор, пока не получим ответ “ДА”.

• Сокращение параметров. Рассматривая \(\operatorname {decision}(I, t)\) для фиксированных \(I, t\), перейти от \(I\) к индивидуальной задаче \(I' = I'(t)\), удаляя те части \(I\), которые заведомо не могут быть использованы в допустимом решении \(\sigma\), для которого \(\operatorname {cost}(\sigma ) \leq t\).

• Нижняя оценка. \(\alpha\)-приближенный алгоритм состоит из 2-х шагов:

  1. семейство примеров \(I(t)\) используется для подсчета нижней оценки на \(\operatorname {OPT}\), назовем ее \(t^{*}\);

  2. находится допустимое решение на примере \(I\left(\alpha \cdot t^{*}\right)\).

Покажем, как технику параметрического сокращения применить к задаче о \(k\)-центрах. Занумеруем ребра графа \(G\) по неубыванию стоимостей, т.е.

\[ \operatorname {cost}\left(e_{1}\right) \leq \operatorname {cost}\left(e_{2}\right) \leq \ldots \leq \operatorname {cost}\left(e_{m}\right), \]

и пусть \(G_{i}=\left(V, E_{i}\right)\), где \(E_{i}=\left\{ e_{1}, e_{2}, \ldots , e_{i}\right\}\).

• Параметризация. Вместо исходной задачи рассматриваем следующую задачу разрешимости \(\operatorname {decision}(I,t)\): для данного \(I = (G, \operatorname {cost}, k)\) и для данного \(t \in \mathbb {Q}_+\) необходимо понять, существует ли в \(G\) такое подмножество вершин \(S \subset V\), что

  \[ \max _{v \in V} \left\{ \operatorname {connect}(v,S)\right\} \leq t \]

  Заметим, что нам достаточно решать \(\operatorname {decision}(I, t)\) для \(t \in \left\{ \operatorname {cost}(e) \mid e \in E\right\}\). Пусть \(t = \operatorname {cost}(e_j)\) для некоторого \(j = 1, \ldots , m\).

• Сокращение параметров. При рассмотрении указанной задачи \(\operatorname {decision}(I,t)\) ребра, стоимость которых больше \(t = \operatorname {cost}(e_j)\), на ответ влиять не будут. Их можно удалить из индивидуальной задачи \(I\): перейти к \(I' = I_j = (G_j, \operatorname {cost}_j, k)\), где

  • \(G_j = (V, E_j)\);

  • \(\operatorname {cost}_j = \operatorname {cost}|_{E_j}\).

  Переходим от \(\operatorname {decision}(I,t)\) к \(\operatorname {decision}(I_j,t)\).

Параметрическое сокращение для задачи о \(k\)-центрах

Решение \(\{s_1,s_2,s_3\}\) (зелёные); синие рёбра — звёзды с центрами в \(S\); красное ребро \(e_j\) — самое дорогое из них. Справа — сокращённый граф \(G_j=(V,\{e_1,\ldots,e_j\})\): убраны все рёбра дороже \(\mathrm{cost}(e_j)\). Наведите курсор на ребро, чтобы узнать, пережило ли оно сокращение.

⇒

\(G\)\(G_j:=(V,\{e_1,\ldots,e_j\})\)

Доминирующим множеством в неориентированном графе \(H=(U, F)\) называется подмножество \(S \subset U\), такое, что каждая вершина из множества \(U \setminus S\) смежна с некоторой вершиной из множества \(S\). Обозначим через \(\operatorname {dom}(H)\) мощность минимального (по мощности) доминирующего множества в \(H\). Заметим, что задача \(\operatorname {decision}(I_j, \operatorname {cost}(e_j))\) является, по сути, задачей проверки неравенства \(\operatorname {dom}(G_j) \leq k\).

Задача о \(k\)-центрах эквивалентна поиску минимального индекса \(j\), такого, что \(G_{j}\) содержит доминирующее множество мощности не более \(k\), т. е. \(G_{j}\) содержит \(k\) звезд, охватывающих все вершины, где звезда это граф \(K_{1, p}, p \geq 1\). Если \(j^{*}\)- это минимальный такой индекс, тогда величина \(\operatorname {cost}\left(e_{j^{*}}\right)\) является оптимальным значением решения задачи о \(k\) центрах. Обозначим эту величину как \(\operatorname {OPT}\).

Сведение исходной задачи к вычислению \(\operatorname {dom}(G_j)\) не может напрямую нам помочь: вычисление мощности доминирующего множества для произвольного графа является NP-трудной задачей.

Независимым множеством в графе \(H=(U, F)\) называется подмножество вершин \(I \subset U\), такое, что в нем нет смежных вершин.

Назовем квадратом графа \(H=(V, F)\) граф \(H^{2}=(V, E)\), такой, что ребро \((u, v) \in E\) тогда и только тогда, когда граф \(H\) содержит путь между вершинами \(u\) и \(v, u \neq v\), длины не более 2.

Квадрат графа

В \(G_j^2\) вершина \(u\) соединена не только со своими соседями (толстые рёбра), но и с их соседями — со всеми, до кого есть путь длины \(\le2\) (светлые дуги). Например, \(u\) и \(u'\) в \(G_j\) не смежны, а в \(G_j^2\) соединены. Наведите курсор на вершину в правой панели.

\(G_j\)\(G_j^2\): звезда \(u\) и новые рёбра через \(u\)

Лемма 1 Пусть дан граф \(H\), и пусть \(I\)- независимое множество в \(H^{2}\). Тогда \(|I| \leq \operatorname {dom}(H)\).

Mn-proofДоказательство

Пусть \(D\) – минимальное доминирующее множество в \(H\), \(\left|D\right| = \operatorname {dom}(H)\). Тогда \(H\) содержит \(|D|\) звезд, охватывающих все вершины. Поскольку каждая из звезд будет кликой в \(H^{2}\), то \(H^{2}\) содержит \(|D|\) клик, содержащих все вершины. Так как в множестве \(I\) может лежать не более одной вершины из каждой клики \(H^{2}\), то \(|I| \leq \operatorname {dom}(H)\).

Доминирующее множество в \(H\) и независимое множество в \(H^2\)

Зелёные кресты — доминирующее множество из 2 вершин. Шаги показывают, почему любое независимое множество в \(H^2\) не больше размера доминирующего множества в \(H\).

Algorithm 1 Алгоритм Хошбаума-Шмойса (\(G = (V,E), \; \operatorname {cost}, \; k\))

• Построить семейство графов \(G_{1}^{2}, G_{2}^{2}, \ldots, G_{m}^{2}\).
• Найти максимальное по включению независимое множество \(I_{r}\) в каждом графе \(G_{r}^{2}\).
• Вычислить наименьший индекс \(r\), такой, что \(\left|I_{r}\right| \leq k\). Пусть это будет \(j\).
• возврат \(I_{j}\).

Лемма 2 Для \(j\), полученного Алгоритмом Хошбаума-Шмойса, верно, что \(\operatorname {cost}\left(e_{j}\right) \leq \operatorname {OPT}\).

Mn-proofДоказательство

Для каждого \(i<j\) имеем, что \(\left|I_{i}\right|>k\). По лемме выше получаем \(\operatorname {dom}\left(G_{i}\right) \geq \left|I_{i}\right|>k\), поэтому \(j^{*}>i\). Это верно для всех \(i < j\), значит, \(j \leq j^{*}\) и \(\operatorname {cost}\left(e_{j}\right) \leq \operatorname {cost}(e_{j^*}) = \operatorname {OPT}\).

Теорема 1 Алгоритм Хошбаума-Шмойса является 2-приближенным алгоритмом для метрической задачи о \(k\)-центрах.

Mn-proofДоказательство

Для начала заметим, что максимальное по включению независимое множество \(I\) в произвольном графе является также и доминирующим (поскольку, если некоторая вершина \(v\) не доминируется никакой из вершин из множества \(I\), то \(I \cup \{ v\}\) является независимым множеством, а это противоречит максимальности \(I\)). Поэтому в графе \(G_{j}^{2}\) найдутся звезды с центрами в вершинах \(I_{j}\), которые охватывают все вершины \(G\). Из неравенства треугольника стоимость ребер в графе \(G_{j}^{2}\) не превосходит \(2 \cdot \operatorname {cost}\left(e_{j}\right)\), так что стоимость решения \(I_j\) не превосходит \(2 \cdot \operatorname {cost}(e_j)\). По лемме выше \(\operatorname {cost}(e_j) \leq \operatorname {OPT}\), откуда стоимость решения не превосходит \(2 \cdot \operatorname {OPT}\).

Приведем пример, который показывает, что эта оценка точна. Пусть задан граф на \(n+1\) вершинах, с одной центральной вершиной. Ребра, смежные с центральной вершиной, имеют стоимость 1, все остальные ребра имеют стоимость 2. Пример графа изображен на рисунке ниже.

Точность оценки 2 алгоритма Хохбаума–Шмойса

Звезда \(K_{1,n}\): рёбра при центре \(c\) стоят \(1\), все остальные — \(2\) (пунктир, показана лишь часть). При \(k=1\) оптимум — центр, \(\mathrm{OPT}=1\). Алгоритм останавливается на \(j\), при котором \(G_j\) — звезда из единичных рёбер, а \(G_j^2\) — полный граф: любая вершина — максимальное независимое множество. Кликните по вершине, чтобы выбрать её центром.

\(n=\)8

Для \(k=1\) оптимальное решение - это центральная вершина, и \(\operatorname {OPT}=1\). Алгоритм Хошбаума-Шмойса получит индекс \(j=n\). Граф \(G_{n}^{2}\)- это полный граф, и если в качестве максимального независимого множества выбрана не центральная вершина, то стоимость решения, полученного алгоритмом, будет 2.

Теорема 2 Для любого \(\varepsilon >0\) не существует \((2-\varepsilon )\)-приближенного алгоритма для метрической задачи о \(k\)-центрах в предположении, что \(P \neq N P\).

Mn-proofДоказательство

Покажем, что если такой алгоритм существует, то он может решать задачу нахождения доминирующего множества за полиномиальное время. Пусть граф \(G=(V, E)\) и число \(k\) являются входными данными задачи доминирующее множество. Построим полный граф \(G^{\prime }=\left(V, E^{\prime }\right)\) с функцией стоимостей

\[ \operatorname {cost}(u, v)= \begin{cases} 1, & \text{ если }(u, v) \in E \\ 2, & \text{ если }(u, v) \notin E\end{cases} \]

Заметим, что граф \(G^{\prime }\) удовлетворяет неравенству треугольника и следующим условиям:

• если \(\operatorname {dom}(G) \leq k\), то \(G^{\prime }\) имеет решение задачи о \(k\)-центрах стоимости 1;

• если \(\operatorname {dom}(G)>k\), то стоимость оптимального решения задачи о \(k\)-центрах в графе \(G^{\prime }\) равна 2.

В первом случае \((2-\varepsilon )\)-приближенный алгоритм должен найти решение стоимости \(1\), поскольку в \((2-\varepsilon )\)-приближенном решении не могут использоваться ребра стоимости 2. Следовательно, такой алгоритм будет решать NP-полную задачу о доминирующем множестве за полиномиальное время.

2 Задача о взвешенных центрах

Технику параметрического сокращения можно использовать и для решения метрической задачи о взвешенных центрах.

Метрическая задача о взвешенных центрах

• полный граф \(G=(V, E)\);

• стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\), такие, что для любых трех вершин \(u, v\) и \(w\) выполняется \(\operatorname {cost}(u, v) \leq\) \(\operatorname {cost}(u, w)+\operatorname {cost}(w, v)\);

• веса вершин \(w: V \rightarrow \mathbf{R}^{+}\) и верхняя граница \(W \in \mathbf{R}^{+}\).

Множество \(S \subseteq V\) суммарного веса \(w(S) \leq W\), которое минимизирует величину \(\max_{v}\{ \operatorname {connect}(v, S)\}\).

Задача о взвешенных центрах

Веса вершин \(1\), \(2\), \(3\) подписаны на вершинах; верхняя граница суммарного веса центров \(W=4\). Зелёные вершины — выбранные центры, жёлтые рёбра — их звёзды. Наведите курсор на вершину, чтобы узнать её вес и центр.

Обозначим через \(w \operatorname {dom}(G)\) вес доминирующего множества минимального веса в графе \(G\). Для решения метрической задачи о взвешенных центрах требуется найти наименьший индекс \(i\), такой, что \(w \operatorname {dom}\left(G_{i}\right) \leq\) \(W\). Пусть это будет индекс \(i^{*}\), тогда стоимость оптимального решения \(\operatorname {OPT}=\operatorname {cost}\left(e_{i^{*}}\right)\).

Рассмотрим вершинно-взвешенный граф \(H\), и пусть \(I\)- независимое множество в графе \(H^{2}\). Для каждого \(u \in I\) обозначим через \(s(u)\) самого легкого соседа вершины \(u\) в графе \(H\) (вершина \(u\) также считается сама для себя соседом). Пусть \(S=\{ s(u) \mid u \in I\}\).

Лемма 3 Для любого вершинно-взвешенного графа \(H\) верно неравенство \(w(S) \leq w \operatorname {dom}(H)\).

Mn-proofДоказательство

Пусть \(D\)- минимальное по весу доминирующее множество в графе \(H\). Тогда в \(H\) существует множество несвязных звезд с центрами в вершинах из \(D\), покрывающих все вершины. Поскольку каждая из звезд становится кликой в графе \(H^{2}\), то \(I\) содержит не более одной вершины из каждой звезды. При этом каждая вершина из \(I\) имеет центр соответствующей звезды как соседнюю вершину в графе \(H\). Для каждой вершины из \(I\) множество \(S\) содержит самого легкого соседа. Следовательно, \(w(S) \leq w(D)\).

В Алгоритме Хошбаума-Шмойса-2 вершина \(s_{i}(u)\) обозначает самого легкого соседа вершины \(u\) в графе \(G_{i}\).

Algorithm 2 Алгоритм Хошбаума-Шмойса-2 (\(G=(V, E), \operatorname {cost} : E \rightarrow \mathbf{Q}^{+}\))

• Построить семейство графов \(G_{1}^{2}, G_{2}^{2}, \ldots, G_{m}^{2}\).
• Найти максимальное независимое множество \(I_{r}\) в каждом графе \(G_{r}^{2}\).
• Построить \(S_{r}=\left\{s_{r}(u) \mid u \in I_{r}\right\}\).
• Вычислить наименьший индекс \(r\), такой, что \(w\left(S_{r}\right) \leq W\). Пусть это будет \(j\).
• возврат \(S_j\).

Теорема 3 Алгоритм Хошбаума-Шмойса-2 является 3-приближенным алгоритмом для метрической задачи о взвешенных центрах.

Mn-proofДоказательство

Покажем, что \(\operatorname {cost}\left(e_{j}\right)\) является нижней оценкой стоимости \(\operatorname {OPT}\). Действительно, для каждого \(i<j\), согласно шагу 4 алгоритма, \(w\left(S_{i}\right)>W\). По лемме выше \(w \operatorname {dom}\left(G_{i}\right) \geq w\left(S_{i}\right)>W\). Следовательно, \(i^{*}>i\) и \(j \leq i^{*}\).

Так как \(I_{j}\) является доминирующим множеством в \(G_{j}^{2}\), то можно покрыть все вершины \(V\) звездами в \(G_{j}^{2}\) с центрами в вершинах \(I_{j}\). Из неравенства треугольника вес ребер в звездах не превосходит \(2 \cdot \operatorname {cost}\left(e_{j}\right)\).

Каждый центр звезды связан с вершиной из \(S_{j}\) ребром стоимости не более чем \(\operatorname {cost}\left(e_{j}\right)\) (рис. ниже). Сдвинем каждый центр в вершину из множества \(S_{j}\), смежную с ним. Из неравенства треугольника получим, что \(\max_{v}\left\{ \operatorname {connect}\left(v, S_{j}\right)\right\} \leq 3 \cdot \operatorname {cost}\left(e_{j}\right)\).

Перераспределение звёзд

Центр звезды \(u\) связан с листьями рёбрами стоимости \(\le\mathrm{cost}(e_i)\) (кроме самого дальнего листа — до него \(\le2\,\mathrm{cost}(e_i)\)); \(s_i(u)\) — самый лёгкий сосед \(u\), с ребром \(\le\mathrm{cost}(e_i)\) до \(u\), а значит, по неравенству треугольника, \(\le3\,\mathrm{cost}(e_i)\) до любого листа (пунктир). Наведите курсор на ребро, чтобы увидеть оценку его стоимости.

Точный пример на оценку 3 для алгоритма Хохбаума–Шмойса-2

Путь \(a\text{-}b\text{-}c\text{-}d\) с единичными рёбрами, веса вершин \(a{:}1,\ b{:}2,\ c{:}2,\ d{:}2\), и \(n\) вершин бесконечного веса, каждая соединена с \(a\) ребром стоимости \(1+\varepsilon\) (остальные расстояния — кратчайшие пути). При \(W=3\) сравните оптимум и то, что может выдать алгоритм.

\(n=\)3

3 Задачи

ProblemЗадача 1

Рассмотрим следующую задачу. Расположить на шахматной доске двух королей так, чтобы минимизировать число ходов от одного из королей до любой клеточки доски. Сформулировать эту задачу как задачу о \(k\)-центрах и решить ее Алгоритмом Хошбаума-Шмойса.

ProblemЗадача 2

Показать, что если стоимости ребер в графе не удовлетворяют неравенству треугольника, то для задачи о \(k\)-центрах не существует \(\alpha (n)\)-приближенного алгоритма для любой полиномиально вычислимой функции \(\alpha (n)\).

ProblemЗадача 3

Рассмотрим шаг 2 Алгоритма Хошбаума-Шмойса, на котором требуется найти максимальное независимое множество в графе \(G_{i}^{2}\). Известны различные способы выбора минимального доминирующего множества. Изменим алгоритм так, чтобы \(I_{r}\) содержало минимальное доминирующее множество в графе \(G_{i}^{2}\). Показать, что новый алгоритм не гарантирует оценку \(2\) для задачи о \(k\)-центрах. Какой гарантированной оценкой точности он обладает?

ProblemЗадача 4

Рассмотрим следующий жадный алгоритм для задачи о \(k\)-центрах.

Algorithm 3 Алгоритм Гонзалеза (\(G=(V, E), \operatorname {cost} : E \rightarrow \mathbf{Q}^{+}\))

• Выбрать произвольную вершину \(v\) и положить \(S=\{v\}\).
• пока \(\left|S\right| < k\) выполнять
  • найти вершину \(v\), максимально удаленную от множества \(S\), т.е. \(\operatorname{connect}(v, S)=\max _{u \in V} \operatorname{connect}(u, S)\).
  • Добавить \(v\) в \(S\).
• возврат \(S\).

Докажите, что Алгоритм Гонзалеза также является \(2\)-приближенным алгоритмом для задачи о \(k\)-центрах.