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

Результаты аппроксимации задачи о 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}} wJ \cdot d(j, \sigma(j))</math>. Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и пользователи» будут в равной степени использоваться для обозначения членов множества <math>\mathcal{D}</math>.