Задача о 1-центре

Задача о 1-центре или минимаксная задача размещения объектов — это классическая задача комбинаторной оптимизации, задача в дисциплине «исследование операций», — частный случай задачи о размещении объектов. В наиболее общем случае формулируется следующим образом:

Задано множество местоположений потребителей, пространство возможных точек размещения объектов (производства или обслуживания) и функция стоимости перевозки от любой точки возможного размещения до точки потребления

Нужно найти оптимальную точку расположения объектов, минимизирующее максимальную стоимость доставки от объекта до потребителя.

Простой частный случай, когда объекты размещения и точки потребления находятся на плоскости, а стоимостью доставки является евклидово расстояние (планарная минимаксная евклидова задача размещения объектов, евклидова задача о 1-центре на плоскости), известна также как задача о наименьшей окружности. Её обобщение на многомерные евклидовы пространства известно как задача о наименьшей ограничивающей сфере. В дальнейшем обобщении (взвешенная евклидова задача размещения) точкам потребления приписаны веса и цена транспортировки является суммой расстояний, умноженных на соответствующие веса. Другой частный случай — задача о ближайшей строке^[англ.], когда входом задачи служит строка, а расстояние измеряется как расстояние Хэмминга.

Существуют многочисленные частные случаи задачи, зависящие как от выбора местоположения точек потребления и объектов производства (или обслуживания), так и от выбора функции, вычисляющей расстояние.

Задача о 1-центре в терминах теории графов

Постановка такого варианта задачи заключается в том, что дан граф ${\displaystyle G=(V,E)}$, ${\displaystyle k\in \mathbb {N} }$ а также функция стоимости ${\displaystyle c\colon E\to \mathbb {Q} ^{+}}$ и необходимо найти множество ${\displaystyle Z\subset V}$ такое, что ${\displaystyle \operatorname {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)}$ для него минимально, т.е. такое множество ${\displaystyle Z}$, что максимальная стоимость пути из ближайшей к любой вершине ${\displaystyle Z}$ вершины останется минимальной. Также задача может быть дополнена фугкцией стоимости вершин ${\displaystyle w\colon V\to \mathbb {Q} ^{+}}$и тогда радиус для нее будет определяться как ${\displaystyle \operatorname {rad} (Z)=\max _{v\in V}[w(v)\cdot \min _{z\in Z}c(z,v)]}$.

Идея приближенного решения задачи заключается в поиске ${\displaystyle Z}$ жадным алгоритмом для фиксированного радиуса ${\displaystyle R}$. Пока существуют вершины, не покрытые ${\displaystyle Z}$, необходимо жадно выбрать вершину ${\displaystyle z}$ и рассматривать все другие вершины в доступности ${\displaystyle 2R}$. Алгоритм повторяется для разных значений ${\displaystyle R}$. Далее приведено описание метода в формальном виде:

1. Установи ${\displaystyle Z=\emptyset }$ и ${\displaystyle U=V}$.
2. Пока ${\displaystyle U\neq \emptyset }$:
   1. ${\displaystyle z=\operatorname {argmax} \{w(u)\mid u\in U\}}$.
   2. ${\displaystyle Z=Z\cup \{z\}}$.
   3. ${\displaystyle U=U\setminus \{v\in U\mid w(v)\cdot \operatorname {dist} (v,z)\leqslant 2R\}}$.
3. Выведи ${\displaystyle Z}$.

Пусть ${\displaystyle R^{*}}$ - оптимальное решение для ${\displaystyle Z^{*}}$. В случае, когда ${\displaystyle R\geqslant R^{*}}$, жадный алгоритм вернет множество ${\displaystyle Z}$ такое, что ${\displaystyle |Z|\leqslant |Z^{*}|}$. Исходя из этого определим ${\displaystyle f(R)=|\operatorname {GreedyCenter} (G,c,w,R)|}$ и заметим, что функция ${\displaystyle f}$ не монотонна. Далее обозначим радуис ${\displaystyle R'=\max _{v\in V}[w(v)\cdot \sum _{e\in E}c(e)]}$, с помощью которого лишь одна вершина в ${\displaystyle Z}$ сможет покрыть все вершины графа, т.е. ${\displaystyle f(R')=1}$, а ${\displaystyle f(0)=|V|=n}$.

Лемма. Для любого графа ${\displaystyle G=(V,E)}$ с оптимальным множеством ${\displaystyle Z^{*}}$ и радиусом ${\displaystyle R^{*}=\operatorname {rad} (Z^{*})}$ справедливо неравенство ${\displaystyle f(R)\leqslant k}$ для всех ${\displaystyle R\geqslant R^{*}}$.

Доказательство. Пусть ${\displaystyle V_{i}=\{v\in V\mid w(v)\cdot \operatorname {dist} (v,z_{i})\leqslant R^{*}\}}$ и ${\displaystyle z\in V_{i}}$ - выбранная вершина в цикле алгоритма ${\displaystyle \operatorname {GreedyCenter} }$. Тогда действительно неравенство:

${\displaystyle {\begin{aligned}w(v)\cdot \operatorname {dist} (v,z)&\leqslant w(v)\cdot (\operatorname {dist} (v,v_{i})+\operatorname {dist} (v_{i},z))\\&\leqslant w(v)\cdot \operatorname {dist} (v,v_{i})+w(z)\cdot \operatorname {dist} (v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{aligned}}}$

Все вершины из ${\displaystyle V_{i}}$ будут удалены в конце итерации, а значит, цикл завершится максимум через ${\displaystyle k=|Z^{*}|}$ итераций, а следовательно ${\displaystyle |Z|\leqslant k}$.

Из леммы следует, что запускать жадный алгоритм можно до тех пор, пока результирующее множество ${\displaystyle Z}$ не станет меньше требуемого ${\displaystyle k}$, используя для вычисления радиусов матрицу расстояний. Таким образом общая временная сложность алгоритма равна ${\displaystyle O(n^{4})}$, а фактор аппроксимации равен ${\displaystyle 2}$.

Разрешимость

При условии неравенства классов P и NP для любого ${\displaystyle r<2}$ не существует полиномиального алгоритма с фактором аппроксимации ${\displaystyle r}$. Доказательство этого утверждения сводится к редукции к задаче о доминирующем множестве: Пусть ${\displaystyle (G,k)}$ подается на вход алгоритму, решающему задачу о доминирующем множестве. Также пусть ${\displaystyle c(e)=1}$ для всех рёбер ${\displaystyle e\in E(G)}$. Тогда ${\displaystyle G}$ содержит домнирующее множество размера ${\displaystyle k}$, если множество ${\displaystyle Z}$ содержит ${\displaystyle k}$ вершин и радиус (${\displaystyle \operatorname {rad} (Z)}$) равен ${\displaystyle 1}$. Если бы существовал ${\displaystyle r}$-аппроксимирующий алгоритм ${\displaystyle {\mathcal {A}}}$ с ${\displaystyle r<2}$, то ${\displaystyle {\mathcal {A}}(G,1,k,c)}$ находил бы доминирующее множество с точно таким же фактором аппроксимации, что невозможно.

См. также

• Задача о размещении объектов с минимизацией суммы расстояний (она же «Задача о 1-медиане») с медианой множества точек^[англ.] в качестве частного случая
• Задача о максиминном размещении объектов (как можно дальше, размещение вредных объектов)
• Задача о k-центре
• Задача о k-медиане