4501
правка
Обобщенная задача построения сети Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обобщенная задача построения сети Штейнера (посмотреть исходный код)
Версия от 18:50, 6 ноября 2017
, 6 ноября 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение | Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение | ||
(3) | (3) <math>0 \le x_e \le 1 \; \; \; \forall e \in E</math> | ||
0 < | |||
Предполагается, что имеется оракул разделения для (LP). Легко увидеть, что такой оракул существует, если (LP) получено из обобщенной задачи построения сети Штейнера. Главный результат, использовавшийся в процессе разработки и анализа алгоритма, представлен в следующей теореме. | Предполагается, что имеется оракул разделения для (LP). Легко увидеть, что такой оракул существует, если (LP) получено из обобщенной задачи построения сети Штейнера. Главный результат, использовавшийся в процессе разработки и анализа алгоритма, представлен в следующей теореме. | ||
'''Теорема 1. В любом базовом решении задачи (LP) имеется по меньшей мере одно ребро e | '''Теорема 1. В любом базовом решении задачи (LP) имеется по меньшей мере одно ребро <math>e \in E \;</math> с <math>x_e \ge 1/2 \;</math>.''' | ||