Минимальные 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) = ( \sum_{i=1}^p (x_i - y_i)^p)^{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 \;</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 (под мультисетью понимается сеть, допускающая наличие ''параллельных'' ребер.

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

Во многих приложениях этой задачи, нередко считающихся наиболее интересными [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>, такое, что для каждого фиксированного " > 0 алгоритм <math>\mathcal{A}_\varepsilon \;</math> исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает <math>(1 + \varepsilon) \;</math>-аппроксимацию.

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

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

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

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

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

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

Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть 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-реберно-связную остовную мультисеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть 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 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Для константного значения d время выполнения рандомизированных алгоритмов составляет nlog n • (1/")O(1) + 2(1/")O(1).

Теорема 8 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть 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 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в <math>(1 + \varepsilon) \;</math> раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 9 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть 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 находит <math>(1 + \varepsilon) \;</math>-аппроксимацию геометрической сети с повышенной живучестью с rv 2 f0; 1; 2g для любого v 2 V. Этот алгоритм может быть дерандомизирован за полиномиальное время.

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

 

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

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