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

В жесткой версии задачи о размещении объектов с ограничением пропускной способности у объекта <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].