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

Все вышеупомянутые цели являются NP-СЛОЖНЫМИ для оптимизации в метрических пространствах общего вида d, что вызвало необходимость изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Алгоритмы аппроксимации для кластеризации на основе метода k-медиан разработаны для пространства d, являющегося неевклидовым метрическим пространством наиболее общего возможного вида. Совокупность F возможных местоположений центров задана в качестве начального условия, множество центров C ограничено C F. С точки зрения аппроксимации ограничение возможных центров конечным множеством F не является чрезмерно строгим: например, для оптимального решения, ограниченного F = D, его целевое значение не более чем в 2 раза превышает оптимальное значение, допускаемое при произвольном F. Обозначим |D| = n и |F| = m. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром > 0. Метрическое пространство d теперь определяется над D [ F.