Минимальные 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.

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

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

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

 

Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к аппроксимационным алгоритмам. Объединяя некоторые идеи, сформулированные Аророй [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> раз превышает оптимальную'''.

Результат теоремы 4 позволяет получить аппроксимационную схему с полиномиальным временем выполнения (PTAS) для малых значений k и d.

'''Теорема 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> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

Сочетая формулировку данной теоремы с тем фактом, что параллельные ребра можно удалить в случае k = 2, получаем следующий результат для задачи 2-связности в сетях.

'''Теорема 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>. Этот алгоритм может быть дерандомизирован за полиномиальное время.'''

Задачи о многосвязности занимают центральное место в алгоритмической теории графов и широко применяются в сферах вычислительных наук и исследования операций – см., например, [1, 13, 11, 18]. Они также играют исключительно важную роль в решении задач о построении сетей, возникающих во многих практических ситуациях [1, 13]. Среди типичных областей применения можно упомянуть телекоммуникации, компьютерные и улично-дорожные сети. Задачи о связности низкой степени для геометрических сетей на плоскости нередко могут достаточно точно аппроксимировать подобные практические задачи (см., например, обсуждение в [13, 17, 18]). Задача построения сети с повышенной живучестью в геометрических сетях также возникает во множестве практических ситуаций – в частности, в телекоммуникациях, при проектировании сетей телекоммуникаций, проектировании СБИС и т.п. [12, 13, 17, 18].

Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего <math>(log \; log \; n)^c</math> для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм аппроксимационной схемы с полиномиальным временем выполнения для больших значений k.

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