Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями

Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект <math>i \in \mathcal{F}</math> может обслуживать не более <math>u_i \;</math> пользователей. В мягком варианте задачи о размещении объектов с ограничением пропускной способности в <math>i \in \mathcal{F}</math> можно открыть <math>r_i \ge 0 \;</math> копий, так что стоимость объекта составит <math>f_i r_i \;</math>, а количество обслуживаемых пользователей – не более <math>r_i u_i \;</math>. Задача оптимизации заключается в выборе значения <math>r_i \;</math> для каждого <math>i \in \mathcal{F}</math> таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности <math>4 + \varepsilon \;</math>.

В жесткой версии задачи о размещении объектов с ограничением пропускной способности у объекта <math>i \in \mathcal{F}</math> имеется строгая граница <math>u_i \;</math> количества объектов, которые могут быть ему назначены. Если пропускная способность <math>u_i \;</math> всех объектов одинакова (однородный случай), Коруполу, Плакстон и Раджамаран [9] представили изящную эвристику локального поиска, основанную на решении задачи о перевозках с промежуточными пунктами и обеспечивающую разрыв локальности <math>8 + \varepsilon \;</math>. Чудак и Уильямсон [4] улучшили анализ этой эвристики, показав, что разрыв локальности составляет <math>6 + \varepsilon \;</math>. В случае неоднородной пропускной способности требуется кардинально иной подход; Пал, Тардош и Уэкслер [14] представили эвристику локального поиска на базе сетевого потока, обеспечивающую разрыв локальности <math>9 + \varepsilon \;</math>. Махдиан и Пал [12] улучшили эту границу до <math>8 + \varepsilon \;</math> за счет обобщения нескольких техник локального поиска, описанных выше, для получения константного коэффициента аппроксимации для варианта задачи о размещении объектов, в которой стоимости объектов являются произвольными неубывающими функциями от потребностей обслуживаемых ими пользователей.

Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 62 3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до <math>(3 + \varepsilon \;)</math>-аппроксимации при помощи локального поиска [1].