Локальный поиск для задачи о 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> за счет обобщения нескольких техник локального поиска, описанных выше, для получения константного коэффициента аппроксимации для варианта задачи о размещении объектов, в которой стоимости объектов являются произвольными неубывающими функциями от потребностей обслуживаемых ими пользователей.