4551
правка
Задача о размещении объектов: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 73: | Строка 73: | ||
UFL | '''UFL''' | ||
Первым алгоритмом с константной гарантией эффективности стал алгоритм аппроксимации с коэффициентом 3,16, разработанный Шмойсом, Тардош и Аардал (см. выше). С тех пор в него были внесены значительные улучшения. Гуха и Хуллер [19, 20] доказали, что нижняя граница аппроксимации составляет 1,463, и предложили жадную процедуру пополнения. Затем была разработана серия алгоритмов аппроксимации на базе LP-округления (см., например, [10, 13]). Существуют также жадные алгоритмы, использующие LP-релаксацию только неявно, для получения нижней границы при анализе прямо-двойственного подхода. В качестве примера можно привести алгоритм аппроксимации JMS с коэффициентом аппроксимации 1,61, разработанный Джейном, Мадьяном и Сабери [29]. Некоторые алгоритмы сочетают несколько разных техник – например, алгоритм аппроксимации Мадьяна, Йе и Чжана [39] с коэффициентом 1,52, использующий алгоритм JMS и жадную процедуру пополнения. Лучшую известную на сегодня гарантию аппроксимации (1,5) получил Бурка [ ]. Она достигается путем сочетания рандомизированного алгоритма LP-округления с жадным алгоритмом JMS. | |||
'''max-UFL''' | |||
Первый алгоритм с константным коэффициентом аппроксимации в 1977 году разработали Корнюжо и др. [15] для задачи max-UFL. Они показали, что при открытии одного объекта за раз жадным образом, выбирая для открытия объект с самой высокой маржинальной прибылью, до тех пор, пока не останется объектов с положительной маржинальной прибылью, алгоритм имеет коэффициент аппроксимации (1 — 1/e) & 0,632. Лучший известный на сегодня коэффициент аппроксимации (0,828) получили Агеев и Свириденко [2]. | |||
'''k-медианы, k-центры''' | |||
Первый алгоритм с константным коэффициентом аппроксимации для задачи о k-медианах был разработан Чарикаром, Гухой, Тардош и Шмойсом [11]. Этот алгоритм LP-округления имеет коэффициент аппроксимации б|. Лучший известный на сегодня коэффициент аппроксимации, 3 + e, при помощи эвристики локального поиска получили Арья и др. [6] (см. также отдельные разделы для метода k-медиан и задачи о размещении объектов). | |||
Первый алгоритм с константным коэффициентом аппроксимации (равным 2) для задачи о k-центрах разработали Хохбаум и Шмойс [26]. Эта гарантия эффективности является наилучшей за исключением случая P = NP. | |||
'''Задача о размещении объектов с ограничениями на пропускную способность''' | |||
Для задачи о размещении объектов с мягкими ограничениями, в которой пропускная способность всех объектов равна, первые алгоритмы аппроксимации с константным коэффициентом разработали Шмойс и др. [51] для обоих вариантов – с возможностью разделения спроса и без таковой возможности (см. выше). Недавно был предложен алгоритм аппроксимации с коэффициентом 2 для решения задачи о размещении объектов с ограничениями на пропускную способность с единичным спросом без возможности разделения, разработанный Мадьяном и др. [39]. Разрыв целостности LP-релаксации для этой задачи также равен 2. Следовательно, для улучшения гарантии аппроксимации необходимо получить улучшенную нижнюю границу в оптимальном решении. | |||
В варианте с жесткими ограничениями на пропускную способность важно разрешить разделение спроса, поскольку в противном случае даже задача существования становится слишком сложной. В случае возможности разделения спроса можно различать случаи с равными значениями пропускной способности, в которых u i = u для всех i 2 F, и общий случай. Для задачи с равными значениями пропускной способности Чудак и Уильямсон получили алгоритм аппроксимации с коэффициентом 5,83 [14]. Первый алгоритм с константным коэффициентом аппроксимации, у = 8:53 + e, для задачи разработали Пал, Тардош и Уэкслер [ ]. Позднее Чжан, Чен и Йе улучшили его, получив коэффициент 5,83 для задачи со значениями пропускной способности общего вида. | |||
'''k-уровневая задача''' | |||
Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [ ], получив у = 3,16. Для k общего вида первый алгоритм с у = 3, предложиди Аардал, Чудак и Шмойс [ ]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом апроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать в при у = 2,523 1 и у = 2,81, соответственно. | |||
1 Это значение у слегка отличается от значения 2,51, приведенного в статье. Исходное рассуждение содержало небольшую ошибку в расчетах. | |||
== Применение == | |||
Задача о размещении объектов широко применяется в области исследования операций. В книге под редакцией Мирчандани и Фрэнсиса [42], а также в книге Немхаузера и Уолси [43] можно найти обзоры и описание способов применения алгоритмов размещения объектов в таких задачах, как размещение заводов и локализации банковских счетов. Недавно эти алгоритмы также нашли применение в таких задачах проектирования сетей, как размещение маршрутизаторов и кэш-памяти [22, 36], агломерация трафика или данных [4, 21], а также репликация веб-серверов в сети распространения контента [31, 45]. | |||
== Открытые вопросы == | |||
