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

Все вышеупомянутые цели являются NP-сложными для оптимизации в метрических пространствах общего вида '''d''', что вызвало необходимость изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Алгоритмы аппроксимации для кластеризации на основе метода k-медиан разработаны для пространства '''d''', являющегося неевклидовым метрическим пространством наиболее общего возможного вида. Совокупность <math>\mathcal{F}</math> возможных местоположений центров задана в качестве начального условия, множество центров C ограничено <math>C \subset \mathcal{F}</math>. С точки зрения аппроксимации ограничение возможных центров конечным множеством <math>\mathcal{F}</math> не является чрезмерно строгим: например, для оптимального решения, ограниченного <math>\mathcal{F} = \mathcal{D}</math>, его целевое значение не более чем в 2 раза превышает оптимальное значение, допускаемое при произвольном <math>\mathcal{F}</math>. Обозначим <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром <math>\varepsilon > 0 \;</math>. Метрическое пространство '''d''' теперь определяется над <math>\mathcal{D} \cup \mathcal{F}</math>.