Минимальные k-связные геометрические сети: различия между версиями

Пусть G = (V, E) – [[геометрическая сеть]], множество вершин V которой соответствует множеству из n точек в пространстве <math>\mathbb{R}^d \;</math> для определенного целого числа <math>d \ge 2 \;</math>, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.

Стоимость <math>\delta(x, y) \;</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R}^d \;</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta(x, y) = \sqrt{ \sum^d_{i=1} (x_i - y_i)^2}</math>, где <math>x = (x_1, ..., x_d) \;</math> и <math>y = (y_1, ..., y_d) \;</math>. В более общем виде стоимость можно определить с использованием других норм – таких как <math>\ell_p</math>-нормы для любого p > 1, т.е. <math>\delta(x, y) = \Big( \sum_{i=1}^p (x_i - y_i)^p \Big)^{1/p} \;</math>. Стоимость сети равна сумме стоимостей всех ребер сети: <math>cost(G) = \sum_{x, y \in E} \delta(x, y) \;</math>.

Сеть G = (V, E) служит [[остов|остовом]] множества точек S (''охватывает'' множество точек S), если V = S. Сеть G является ''k-вершинно-связной'', если для любого множества <math>U \subseteq V \;</math>, состоящего из менее чем k вершин, сеть <math>(V \backslash U, E \cap ((V \backslash U) \times (V \backslash U))</math> является связной. Подобным же образом G является ''k-реберно-связной'', если для любого множества <math>\mathcal{E} \subseteq E \;</math> с количеством ребер менее k сеть <math>(V, E \backslash \mathcal{E}) \;</math> является связной.

Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-вершинно-связную евклидову сеть минимальной стоимости, охватывающую точки S.

Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S.

 

 

Рассматривается также вариант, допускающий наличие [[параллельные ребра|параллельных ребер]]:

Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие параллельных ребер.

Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность [[Евклидова_задача_Штейнера|евклидовой сети Штейнера]], если разрешить использование дополнительных вершин, называемых [[точки Штейнера|точками Штейнера]]. Для заданного набора точек S в пространстве <math>\mathbb{R}^d \;</math> геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является [[надмножество|надмножеством]] S и для каждой пары точек из S существует k внутренне вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G.

'''(Евклидова) задача нахождения k-вершинно/реберно-связной сети Штейнера минимальной стоимости'''

Найти сеть минимальной стоимости на надмножестве S, являющуюся k-вершинно/реберно-связной сетью Штейнера для S.

В более общей формулировке задач о многосвязности в графах следует учитывать неоднородные ограничения связности.

'''Задача построения сети с повышенной живучестью'''

Для заданного набора S точек в <math>\mathbb{R}^d \;</math> и функции требования связности <math>r: S \times S \to \mathbb{N} \;</math> найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин <math>p, q \in S \;</math> подсеть имеет <math>r_{p, q} \;</math> внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.

Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности <math>r_v \in \mathbb{N} \;</math>. Тогда для любой пары вершин <math>p, q \in S \;</math> требование связности <math>r_{p, q} \;</math> задается просто в виде <math>min \{ r_p, r_q \} \;</math> [12, 13, 17, 18]. В число таких приложений входит задача о вычислении [[дерево Штейнера|дерева Штейнера]], (см., например, [2]), в которой <math>r_p \in \{ 0, 1 \} \;</math> для любой вершины <math>p \in S \;</math>.

''Аппроксимационная схема с полиномиальным временем выполнения'' (PTAS) представляет собой семейство алгоритмов <math>\{ \mathcal{A}_\varepsilon \} \;</math>, такое, что для каждого фиксированного <math>\varepsilon > 0 \;</math> алгоритм <math>\mathcal{A}_\varepsilon \;</math> исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает <math>(1 + \varepsilon) \;</math>-аппроксимацию.

Исчерпывающий обзор результатов решения задач о нахождении k-вершинно-связных или k-реберно-связных остовных подграфов с минимальной стоимостью, задач о неоднородной связности, задач о пополнении связности и геометрических задач приведен в работах [1, 3, 11, 15].

Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных аппроксимационных алгоритмов этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем <math>\frac{3}{2}</math> (где <math>\frac{3}{2}</math> – это наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).

Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [10]) на геометрические сети.

'''Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NP-полной.'''

Следующий результат показывает, что если рассматривать задачи о многосвязных объектах минимальной стоимости при достаточно большой размерности, эти задачи становятся APX-полными.

'''Теорема 2 ([6]). Существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в <math>\mathbb{R}^{\lceil log_2 \; n \rceil}</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.'''

Этот результат также можно расширить на любую <math>\ell_p</math>--норму.

'''Теорема 3 ([6]). Для любого целого числа <math>d \ge log \; n</math> и любого фиксированного <math>p \ge 1 \;</math> существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике <math>\ell_p</math>- в пространстве <math>\mathbb{R}^d \;</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.'''

Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к аппроксимационным алгоритмам. Объединяя некоторые идеи, сформулированные Аророй [2] (см. также [6]) для аппроксимационных алгоритмов задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.

'''Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, <math>k, d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot (log \; n)^{(kd / \varepsilon)^{O(d)}} \cdot 2^{2^{(kd / \varepsilon)^{O(d)}}}</math> с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную'''.

'''Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную.'''

Заметим, что в случае, если все значения d, k и <math>\varepsilon \;</math> являются константными, время выполнения составляет <math>n \cdot log^{O(1)} \; n</math>.

 

'''Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть <math>d \ge 2 \;</math> – любое константное целое число. Существует определенная положительная константа <math>c < 1 \;</math>, такая, что для всех <math>k \le (log \; log \; n)^c</math> задача построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве <math>\mathbb{R}^d \;</math> допускает использование PTAS.'''

'''Теорема 6 ([5]). Пусть k и d – любые целые числа, <math>k, d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{2^{(k^{O(1)} \cdot d / \varepsilon)^{O(d^2)})}}</math> с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

'''Теорема 7 (Аппроксимационные схемы для 2-связных графов, [5]). Пусть d – любое целое число, <math>d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}}</math> с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

Для константного значения d время выполнения рандомизированных алгоритмов составляет <math>n \; log \; n \cdot (1 / \varepsilon)^{O(1)} + 2^{(1 / \varepsilon)^{O(1)}}</math>.

'''Теорема 8 ([7]). Пусть d – любое целое число, <math>d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}}</math> с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

 

'''Теорема 9 ([7]). Пусть d – любое целое число, <math>d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}}</math> с вероятностью не менее 0,99 находит <math>(1 + \varepsilon) \;</math>-аппроксимацию геометрической сети с повышенной живучестью с <math>r_v \in \{ 0, 1, 2 \} \;</math> для любого <math>v \in V \;</math>. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

 

 

 

 

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