4511
правок
Обобщенная задача построения сети Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
Обобщенная задача построения сети Штейнера (посмотреть исходный код)
Версия от 13:44, 6 ноября 2017
, 6 ноября 2017→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Построение сети с повышенной живучестью == Постановка зада…») |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф G = (V, E), в котором каждое ребро e | Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф G = (V, E), в котором каждое ребро <math>e \in E \;</math> имеет неотрицательную стоимость cost c(e), а для каждой пары вершин <math>i, j \in V \;</math> имеется требование связности <math>r_{i,j} \in \mathbb{Z} \;</math>. Допустимое решение представляет собой подмножество ребер <math>E' \subseteq E \;</math>, такое, что каждая пара вершин <math>i, j \in V \;</math> соединена по меньшей мере <math>r_{i,j} \;</math> реберно-непересекащихся путей в графе G' = (V, E'). | ||
Обобщенная задача построения сети Штейнера заключается в нахождении решения | Обобщенная задача построения сети Штейнера заключается в нахождении решения E' с минимальной стоимостью <math>\sum_{e \in E'} c(e) \;</math>. | ||
| Строка 15: | Строка 15: | ||
Уильямсон и др. [ ] первыми представили нетривиальный алгоритм аппроксимации для обобщенной задачи построения сети Штейнера, получив 2k-аппроксимацию, где k = | Уильямсон и др. [8] первыми представили нетривиальный алгоритм аппроксимации для обобщенной задачи построения сети Штейнера, получив 2k-аппроксимацию, где <math>k = max_{i,j \in V} \{ r_{i, j} \} \;</math>. Этот результат был улучшен до O(log k)-аппроксимации в работе Геманса и др. [3]. | ||
== Основные результаты == | == Основные результаты == | ||