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

Теорема 2 ([6]). Существует константа £ > 0, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в Rdlog2ne, с коэффициентом 1 + % является NPT-полной.

Теорема 3 ([6]). Для любого целого числа d > log n и любого фиксированного p > 1 существует константа £ > 0, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике lp в пространстве Rd, с коэффициентом 1 + % является NP-полной.

Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время

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

Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 0(kd/")O(d) с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 8 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2{dls)°{i2) + n-22i с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 9 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2ldle)°(d ) + n-22d с вероятностью не менее 0,99 находит (1 + ")-аппроксимацию геометрической сети с повышенной живучестью с rv 2 f0; 1; 2g для любого v 2 V. Этот алгоритм может быть дерандомизирован за полиномиальное время.