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

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров <math>C_t \;</math>. В задаче о k-медианах эта совокупность удовлетворяет условию <math>|C_t| = k \;</math>. На этапе локального улучшения вначале генерируется совокупность решений <math>\mathbb{E}_{t+1}</math> из <math>C_t \;</math>. Это выполняется таким образом, что <math>|\mathcal{E}_{t+1}|</math> оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент <math>C \in \mathcal{E}_{t+1}</math> удовлетворяет условию |C| = k. На этапе улучшения полагаем <math>C_{t+1} = argmin_{C \in \mathcal{E}_{t+1}} f(C)</math>. Для предварительно заданного параметра <math>\varepsilon > 0 \;</math> итерации улучшений останавливаются на первом этапе T, для которого выполняется <math>f(C_T) \ge (1 - \varepsilon) f(C_{T - 1}) \;</math>.