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

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