4551
правка
Обобщенная задача построения сети Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обобщенная задача построения сети Штейнера (посмотреть исходный код)
Версия от 13:48, 6 ноября 2017
, 6 ноября 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
2-аппроксимация получена для более общей задачи, которая формулируется следующим образом. Пусть имеется мультиграф G = ( | 2-аппроксимация получена для более общей задачи, которая формулируется следующим образом. Пусть имеется мультиграф G = (V, E) с ребрами стоимостью <math>c( \cdot ) \;</math> и функция требований связности <math>f: 2^V \to \mathbb{Z} \;</math>. Функция f является слабо субмодулярной, т.е. имеет следующие свойства: | ||
1. f(V) = 0. | 1. f(V) = 0. | ||
2. Для любых A, B | 2. Для любых <math>A, B \subseteq V \;</math> выполняется по меньшей мере одно из двух следующих условий: | ||
<math>f(A) + f(B) \le f(A \backslash B) + f(B \backslash A) \;</math>; | |||
<math>f(A) + f(B) \le f(A \cap B) + f(A \cup B)</math>. | |||
| Строка 64: | Строка 64: | ||
Пусть дано любое решение (LP). Множество S С V называется плотным в том и только том случае, если ограничение (1) удовлетворяется для S в виде равенства. Доказательство теоремы 1 включает построение большого ламинарного семейства плотных множеств (семейства, в котором для любой пары множеств либо одно множество содержит другое, либо множества не пересекаются). После этого применяется продуманная схема учета, которая назначает ребра множествам ламинарного семейства, чтобы показать, что существует по меньшей мере одно ребро e 2 E с xe > 1/2. | Пусть дано любое решение (LP). Множество S С V называется плотным в том и только том случае, если ограничение (1) удовлетворяется для S в виде равенства. Доказательство теоремы 1 включает построение большого ламинарного семейства плотных множеств (семейства, в котором для любой пары множеств либо одно множество содержит другое, либо множества не пересекаются). После этого применяется продуманная схема учета, которая назначает ребра множествам ламинарного семейства, чтобы показать, что существует по меньшей мере одно ребро e 2 E с xe > 1/2. | ||
== Применение == | == Применение == | ||