Локальный поиск для задачи о 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>. Обозначим |D| = n и |F| = m. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром > 0. Метрическое пространство '''d''' теперь определяется над D [ F.