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

Все вышеупомянутые цели являются NP-сложными для оптимизации в метрических пространствах общего вида '''d''', что привело к необходимости изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Алгоритмы аппроксимации для кластеризации на основе метода k-медиан разработаны для метрического пространства '''d''' общего вида, возможно, являющегося неевклидовым. Совокупность <math>\mathcal{F}</math> возможных местоположений центров задана в качестве начального условия, множество центров C ограничено <math>C \subseteq \mathcal{F}</math>. С точки зрения аппроксимации ограничение возможных центров конечным множеством <math>\mathcal{F}</math> не является чрезмерно строгим: например, для оптимального решения, ограниченного <math>\mathcal{F} = \mathcal{D}</math>, целевое значение не более чем в 2 раза превышает оптимальное значение при произвольном <math>\mathcal{F}</math>. Обозначим <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром <math>\varepsilon > 0 \;</math>. Метрическое пространство '''d''' теперь определяется над <math>\mathcal{D} \cup \mathcal{F}</math>.

Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр i … Ct и удалить множество I(i), вычисляет 3 + "-аппроксимацию с высокой вероятностью за T = O(N log N(log N + 1/")) этапов улучшения, каждый из которых занимает O(N) времени.

Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект i 2 F может обслуживать не более ui пользователей. В случае мягкого варианта задачи о размещении объектов с ограничением пропускной способности ri _ 0 можно открыть в i 2 F, так что стоимость объекта составит fi ri, а количество обслуживаемых пользователей – не более riui . Задача оптимизации заключается в выборе значения ri для каждого i 2 F таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности 4 + ".

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

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