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