4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:18, 27 апреля 2018
, 27 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 79: | Строка 79: | ||
Множество I(i) вычисляется следующим образом. Обозначим за W множество элементов, расположенных ближе к i, чем к назначенным им центрам в | Множество I(i) вычисляется следующим образом. Обозначим за W множество элементов, расположенных ближе к i, чем к назначенным им центрам в <math>C_t \;</math>. При вычислении I(i) этими элементами можно пренебречь. Для каждого центра <math>s \in C_t \;</math> обозначим за <math>U_s \;</math> все элементы, назначенные s. Если <math>f_s + \sum_{j \in U_s \backslash W} d_j d(j, s) > \sum_{j \in U_s \backslash W} d_j d(j, i)</math>, то дешевле удалить объект s и переназначить элементы из <math>U_s \backslash W \;</math> элементу i. В этом случае s размещается в I(i). Обозначим N = m + n. Таким образом, процедура вычисления I(i) требует O(N) времени, что делает общее время выполнения полиномиальным. Чарикар и Гуха [2] сформулировали следующую теорему. | ||