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

Сеть 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 (под мультисетью понимается сеть, допускающая наличие ''параллельных'' ребер.

Понятие 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.

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

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

 

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

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