4551
правка
Задача о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Основные результаты == | == Основные результаты == | ||
Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации , основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии <math>\gamma \;</math>. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55]. | Для решения задач о размещении объектов было предложено множество алгоритмов. Вначале будет приведено краткое описание алгоритмов Шмойса, Тардош и Аардал [51]. Затем будет представлен сжатый обзор основных результатов. Некоторые алгоритмы, дающие наилучшие значения гарантии аппроксимации <math>\gamma \;</math>, основаны на решении задачи LP-релаксации при помощи полиномиального алгоритма, что может потребовать значительного времени; в то же время некоторые авторы предложили быстрые комбинаторные алгоритмы для задач о размещении объектов с менее привлекательными значениями гарантии <math>\gamma \;</math>. В свете ограничений на объем занимаемой памяти более эффективно уделять внимание алгоритмам, обеспечивающим наилучшие значения гарантии аппроксимации. Дополнительные ссылки можно найти в обзорных статьях Шмойса [49,50] и Вайгена [55]. | ||