Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
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 для задачи со значениями пропускной способности общего вида. | В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>, и общий случай. Для задачи с равными значениями пропускной способности Чудак и Уильямсон получили алгоритм аппроксимации с коэффициентом 5,83 [14]. Первый алгоритм с константным коэффициентом аппроксимации, <math>\gamma = 8,53 + \epsilon \;</math>, для общей задачи разработали Пал, Тардош и Уэкслер [44]. Позднее Чжан, Чен и Йе [57] улучшили его, получив коэффициент 5,83 для задачи со значениями пропускной способности общего вида. | ||
'''k-уровневая задача''' | '''k-уровневая задача''' | ||
Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [ ], получив | Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [51], получив <math>\gamma = 3,16 \;</math>. Для k общего вида первый алгоритм с <math>\gamma = 3 \;</math> предложили Аардал, Чудак и Шмойс [1]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом аппроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать в при <math>\gamma = 2,523 \;</math>* и <math>\gamma = 2,81 \;</math>, соответственно. | ||
''(* Это значение у слегка отличается от значения 2,51, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах)''. | |||
== Применение == | == Применение == | ||