4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:59, 19 апреля 2018
, 19 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
Теорема 1 ([1]). Эвристика с p заменами обеспечивает разрыв локальности (3 + 2/p) + | '''Теорема 1 ([1]). Эвристика с p заменами обеспечивает разрыв локальности <math>(3 + 2/p) + \varepsilon \;</math>, а время выполнения составляет <math>O(nk(log(nD))/\varepsilon(mk)^p) \;</math>. Кроме того, для любого значения p существует экземпляр задачи о k-медианах, в которой эвристика с p заменами обеспечивает разрыв локальности, в точности равный (3 + 2/p).''' | ||
Положив p = 1/ | Положив <math>p = 1 / \varepsilon \;</math>, получим, что вышеописанная эвристика имеет коэффициент аппроксимации <math>3 + \varepsilon \;</math> и время выполнения <math>\tilde{O}(n(mk)^{O(1/\varepsilon)})</math>. | ||
'''Задача о размещении объектов''' | '''Задача о размещении объектов''' | ||
Поскольку в этой задаче уже нет ограничения на количество центров, этап локального улучшения требует соответствующей модификации. Были разработаны две эвристики локального поиска, обеспечивающие разрыв локальности <math>3 + \varepsilon \;</math> за полиномиальное время. | |||
Эвристика | |||
Эвристика «''добавление, удаление и замена''», предложенная Кюном и Хамбургером [10], добавляет центр в <math>C_t \;</math>, исключает центр из <math>C_t \;</math> либо заменяет центр из <math>C_t \;</math> центром из <math>\mathcal{F} \backslash C_t</math>. Начальное множество <math>C_0 \;</math> также выбирается произвольно. | |||
Et+1 = f(Ct nA) [ B; где A jAj = 0; jBj = 1 или jAj = 1; jBj = 0; или jAj = 1; jBj = 1g | Et+1 = f(Ct nA) [ B; где A jAj = 0; jBj = 1 или jAj = 1; jBj = 0; или jAj = 1; jBj = 1g | ||