4551
правка
Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 96: | Строка 96: | ||
В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых | В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>, и общий случай. Для задачи с равными значениями пропускной способности Чудак и Уильямсон получили алгоритм аппроксимации с коэффициентом 5,83 [14]. Первый алгоритм с константным коэффициентом аппроксимации, <math>\gamma = 8,53 + \epsilon \;</math>, для задачи разработали Пал, Тардош и Уэкслер [44]. Позднее Чжан, Чен и Йе [57] улучшили его, получив коэффициент 5,83 для задачи со значениями пропускной способности общего вида. | ||