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

Для второго этапа используется понятие ''кластеризации'', позднее формализованное Чудаком и Шмойсом [13]. Основываясь на дробном решении, экземпляр разбивается на фрагменты, называемые ''кластерами''. У каждого кластера имеется отдельный клиент, называемый ''центром кластера''. Процесс выполняется путем итеративного выбора клиента, не охваченного предыдущими кластерами, в качестве центра кластера, и добавления к этому кластеру объектов, обслуживающих этого клиента в дробном решении, а также других клиентов, обслуживаемых этими объектами. Такое построение кластеров гарантирует, что общая сумма открытых в каждом кластере объектов равна единице и, следовательно, после открытия объекта с наименьшей возможной стоимостью в каждом кластере суммарная уплаченная стоимость открытия объекта не превышает стоимость открытия объекта у дробного решения. Более того, выбирая клиентов в качестве центров кластеров жадным образом, алгоритм добивается того, чтобы каждый центр кластера минимизировал определенную стоимостную функцию для клиентов кластера. Оставшиеся клиента кластера также соединяются с открытым объектом. Для ограничения стоимости этого соединения используется неравенство треугольника для стоимостей соединений. Для задачи UFL этот алгоритм фильтрации и округления представляет собой алгоритм 4-аппроксимации, Шмойс и др. Также показали, что в случае замены этапа фильтрации ''рандомизированной фильтрацией'' можно получить гарантию аппроксимации 3,16.

Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т. е. <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>. В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и <math>\gamma' \ge 1 \;</math>. Заметим, что <math>\gamma' \;</math> не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность <math>\gamma' u \;</math> со стоимостью <math>\gamma' f_i \;</math>. Алгоритм <math>(\gamma, \gamma') \;</math>-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в <math>\gamma \;</math> раз превышает истинную оптимальную стоимость, имеющую место в случае <math>y \in \{0, 1 \}^{n_f} \;</math>. Шмойс и др. разработали алгоритм (5,69< 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62< 4,29)-аппроксимации для варианта без возможности разделения.

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