4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:51, 19 апреля 2018
, 19 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Вышеописанное обозначает простую замену не более чем p центров из Ct тем же количеством центров из F | Вышеописанное обозначает простую замену не более чем p центров из Ct тем же количеством центров из <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. | ||