4551
правка
Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Основные результаты == | == Основные результаты == | ||
Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [ ]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации у, основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии y. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55]. | |||
'''Алгоритмы Шмойса, Тардош и Аардал''' | |||
Вначале будет представлен алгоритм решения задачи UFL, а затем перечислены результаты, которые могут быть получены за счет адаптации алгоритма к другим задачам. | |||
Алгоритм выполняет LP-релаксацию, а затем в два этапа модифицирует полученное дробное решение. Первый этап, называемый фильтрацией, предназначен для ограничения стоимости соединения каждого клиента с самым удаленным объектом, частично обслуживающим его. Для этого переменные yi, обозначающие стоимость открытия объектов, пропорционально увеличиваются на константную величину, а затем переменные xij, обозначающие стоимость соединения, корректируются для использования ближайших возможных объектов. | |||
Для второго этапа используется понятие кластеризации, позднее формализованное Чудаком и Шмойсом [13]. Основываясь на дробном решении, экземпляр разбивается на фрагменты, называемые кластерами. У каждого кластера имеется отдельный клиент, называемый центром кластера. Это производится путем итеративного выбора клиента, не охваченного предыдущими кластерами, в качестве центра кластера, и добавления к этому кластеру объектов, обслуживающих этого клиента в дробном решении, а также других клиентов, обслуживаемых этими объектами. Такое построение кластеров гарантирует, что объекты в каждом кластере открыты для количества клиентов, в сумме равного единице и, следовательно, после открытия объекта с наименьшей возможной стоимостью в каждом кластере суммарная уплаченная стоимость открытия объекта не превышает стоимость открытия объекта у дробного решения. Более того, выбирая клиентов в качестве центров кластеров жадным образом, алгоритм добивается того, чтобы каждый центр кластера минимизировал определенную стоимостную функцию для клиентов кластера. Оставшиеся клиента кластера также соединяются с открытым объектом. Для ограничения стоимости этого соединения используется неравенство треугольника для стоимостей соединений. Для задачи UFL этот алгоритм фильтрации и округления представляет собой алгоритм 4-аппроксимации, Шмойс и др. Также показали, что в случае замены этапа фильтрации рандомизированной фильтрацией можно получить гарантию аппроксимации 3,16. | |||
В той же статье была выполнена адаптация алгоритма, с применением рандомизированной фильтрации и без нее, с целью получения алгоритмов аппроксимации для задачи о размещении объектов с мягкими ограничениями на пропускную способность, а также для двухуровневой задачи о размещении объектов без ограничений на пропускную способность. Далее будут обсуждаться результаты работы алгоритма с применением рандомизированной фильтрации. | |||
Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т.е. ui = u для всех i 2 F . В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и y' > 1. Заметим, что y' не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность y'u со стоимостью y'fi. Алгоритм (y, y')-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в у раз превышает истинную оптимальную стоимость, а именно, с 2 f0; 1gnf. Шмойс и др. разработали алгоритм (5,69; 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62; 4,29)-аппроксимации для варианта без возможности разделения. | |||
Во второй модели о размещении объектов с мягкими ограничениями на пропускную способность задача меняется таким образом, чтобы y-переменные могли принимать неотрицательные целочисленные значения, благодаря чему можно открывать несколько объектов с пропускной способностью u в каждом местоположении. Алгоритмы аппроксимации в данном случае дают решение, являющееся допустимым в рамках данной модифицированной модели. Легко показать, что гарантии аппроксимации, полученные для предыдущей модели, выполняются и в данном случае – речь идет о полученных Шмойсом алгоритмах 5,69-аппроксимации для варианта с возможностью разделения спроса и 7,62-аппроксимации для варианта без возможности разделения спроса. Последняя модель чаще всего рассматривается в более современных работах, поэтому именно на нее будут ссылаться авторы в параграфе, посвященном размещению объектов с мягкими ограничениями на пропускную способность. | |||
UFL | |||