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

Для заданного множества 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>-аппроксимацию.