4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 23:24, 15 сентября 2016
, 15 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к алгоритмам аппроксимации. Объединяя некоторые идеи, | Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к алгоритмам аппроксимации. Объединяя некоторые идеи, сформулированные Аророй [ ] (см. также [ ]) для алгоритмов аппроксимации задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты. | ||
Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время | Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время | ||
n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не | n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. | ||
Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не | Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. | ||
| Строка 98: | Строка 98: | ||
Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 0(kd/")O(d) с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не | Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 0(kd/")O(d) с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время. | ||
| Строка 104: | Строка 104: | ||
Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не | Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время. | ||
| Строка 110: | Строка 110: | ||
Теорема 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, стоимость которой не | Теорема 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 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время. | ||