4551
правка
Задача о размещении объектов: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 101: | Строка 101: | ||
'''k-уровневая задача''' | '''k-уровневая задача''' | ||
Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [51], получив <math>\gamma = 3,16 \;</math>. Для k общего вида первый алгоритм с <math>\gamma = 3 \;</math> предложили Аардал, Чудак и Шмойс [1]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом аппроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать | Первый алгоритм с константным коэффициентом аппроксимации для 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, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах)''. | ''(* Это значение у слегка отличается от значения 2,51, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах)''. | ||
