Задача о размещении объектов: различия между версиями

Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации у, основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии y. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55].