Локальный поиск для задачи о 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>.

Родственной для задачи о k-медианах является задача лагранжевой релаксации под названием «[[задача о размещении объектов]]». В этой задаче также имеется совокупность <math>\mathcal{F}</math> возможных местоположений центров. Каждое местоположение <math>i \in \mathcal{F}</math> имеет стоимость <math>r_i \;</math>. Задача заключается в выборе совокупности <math>C \subseteq \mathcal{F}</math> центров и построении отображения <math>\sigma: S \to C</math> элементов на центры, при котором следующая функция достигает минимума:

Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, в котором каждому элементу <math>j \in \mathcal{D}</math> разрешается иметь неотрицательный вес <math>w_j \;</math>. В формулировке целевой функции <math>f(C) \;</math> компонент <math>\sum_{j \in \mathcal{D}} d(j, \sigma(j))</math> заменяется на <math>\sum_{j \in \mathcal{D}} w_j \cdot d(j, \sigma(j))</math>. Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и «пользователи» будут в равной степени использоваться для обозначения членов множества <math>\mathcal{D}</math>.

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров <math>C_t \;</math>. В задаче о k-медианах эта совокупность удовлетворяет условию <math>|C_t| = k \;</math>. На этапе локального улучшения вначале генерируется совокупность решений <math>\mathcal{E}_{t+1}</math> из <math>C_t \;</math>. Это выполняется таким образом, что <math>|\mathcal{E}_{t+1}|</math> оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент <math>C \in \mathcal{E}_{t+1}</math> удовлетворяет условию <math>|C| = k \;</math>. На этапе улучшения полагаем <math>C_{t+1} = argmin_{C \in \mathcal{E}_{t+1}} f(C)</math>. Для предварительно заданного параметра <math>\varepsilon > 0 \;</math> итерации улучшений останавливаются на первом этапе T, для которого выполняется соотношение <math>f(C_T) \ge (1 - \varepsilon) f(C_{T - 1}) \;</math>.

Основными проблемами разработки являются конкретизация начального множества <math>C_0 \;</math> и построение <math>\mathcal{E}_{t+1}</math> из <math>C_t \;</math>. Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения <math>f(C_T) \;</math> по отношению к оптимальному решению <math>f(C^*) \;</math>. Соотношение <math>(f(C_T))/( f(C^*)) \;</math> называется «разрывом локальности» эвристики.

Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это «''естественная эвристика с p заменами''»: пусть имеется текущее множество центров <math>C_t \;</math> размера k; множество <math>\mathcal{E}_{t+1}</math> определяется следующим образом:

Вышеописанное обозначает простую замену не более чем p центров из <math>C_t \;</math> тем же количеством центров из <math>\mathcal{F} \backslash C_t</math>. Вспомним, что <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Очевидно, <math>|\mathcal{E}_t+1| \le (k(m - k))^p \le (km)^p</math>. Начальное множество <math>C_0 \;</math> выбирается произвольным образом. Значение p является параметром, от которого зависят время выполнения и коэффициент аппроксимации. Он выбирается константным, так что <math>|\mathcal{E}t|</math> является полиномом от m.

<math>\mathcal{E}_{t + 1} = \{(C_t \backslash \mathcal{A}) \cup \mathcal{B},</math> где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = 0, |\mathcal{B}| = 1,</math> либо <math>|\mathcal{A}| = 1, |\mathcal{B}| = 0,</math> либо <math>|\mathcal{A}| = 0, |\mathcal{B}| = 1 \}.</math>

Очевидно, <math>|\mathcal{E}_{t + 1}| = O(m^2)</math>, что делает время выполнения полиномиальным от размера входных данных и значения <math>1/ \varepsilon \;</math>. Коруполу, Плакстон и Раджамаран [9] показали, что эта эвристика обеспечивает разрыв локальности не более <math>5 + \varepsilon \;</math>. Арья и др. [1] выполнили более строгий анализ, показав, что эвристика достигает разрыва локальности <math>3 + \varepsilon \;</math> и что эта граница является точной в том смысле, что существуют экземпляры задачи, для которых разрыв локальности строго равен 3.

Эвристика «''добавить один, удалить несколько''», предложенная Чарикаром и Гухой [2], несколько сложнее. Она добавляет один объект и отбрасывает все объекты, которые становятся несущественными в новом решении.

 

 

 

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

Эвристики локального поиска также называются вариантами задач о 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-медианах первая аппроксимация с константным коэффициентом 6 2/3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до <math> \; (3 + \varepsilon)</math>-аппроксимации при помощи локального поиска [1].