Обобщенная задача построения сети Штейнера: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 54: Строка 54:


Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение
Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение
8e 2E
 
(3)
(3) <math>0 \le x_e \le 1 \; \; \; \forall e \in E</math>
0 < xe < 1
 


Предполагается, что имеется оракул разделения для (LP). Легко увидеть, что такой оракул существует, если (LP) получено из обобщенной задачи построения сети Штейнера. Главный результат, использовавшийся в процессе разработки и анализа алгоритма, представлен в следующей теореме.
Предполагается, что имеется оракул разделения для (LP). Легко увидеть, что такой оракул существует, если (LP) получено из обобщенной задачи построения сети Штейнера. Главный результат, использовавшийся в процессе разработки и анализа алгоритма, представлен в следующей теореме.




'''Теорема 1. В любом базовом решении задачи (LP) имеется по меньшей мере одно ребро e 2 E с xe > 1/2.'''
'''Теорема 1. В любом базовом решении задачи (LP) имеется по меньшей мере одно ребро <math>e \in E \;</math> с <math>x_e \ge 1/2 \;</math>.'''




4431

правка

Навигация