Задача о размещении объектов: различия между версиями

Во второй модели задачи о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, благодаря чему можно открывать несколько объектов с пропускной способностью u в каждом местоположении. Алгоритмы аппроксимации в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность.

Первым алгоритмом с константной гарантией эффективности стал алгоритм аппроксимации с коэффициентом 3,16, разработанный Шмойсом, Тардош и Аардал (см. выше). С тех пор в него были внесены значительные улучшения. Гуха и Хуллер [19, 20] доказали, что нижняя граница аппроксимации составляет 1,463, и предложили жадную процедуру пополнения. Затем была разработана серия алгоритмов аппроксимации на базе LP-округления (см., например, [10, 13]). Существуют также жадные алгоритмы, использующие LP-релаксацию только неявно, для получения нижней границы при анализе прямо-двойственного подхода. В качестве примера можно привести алгоритм аппроксимации JMS с коэффициентом аппроксимации 1,61, разработанный Джейном, Мадьяном и Сабери [29]. Некоторые алгоритмы сочетают несколько разных техник – например, алгоритм аппроксимации Мадьяна, Йе и Чжана [39] с коэффициентом 1,52, использующий алгоритм JMS и жадную процедуру пополнения. Лучшую известную на сегодня гарантию аппроксимации (1,5) получил Бурка [ ]. Она достигается путем сочетания рандомизированного алгоритма LP-округления с жадным алгоритмом JMS.