Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 37: | Строка 37: | ||
'''Графы с ограниченной независимостью''' | '''Графы с ограниченной независимостью''' | ||
В работах [3, 4, 5] изучаются алгоритмы | В работах [3, 4, 5] изучаются локальные аппроксимационные алгоритмы для задач о покрытии и упаковке для графов, встречающихся в контексте беспроводных децентрализованных сетей и сетей датчиков. Из-за их масштаба, динамичности и ограниченности ресурсов такие сети представляют собой особенно интересную область для применения локальных распределенных алгоритмов. | ||
Строка 95: | Строка 95: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с алгоритмами | Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с распределенными аппроксимационными алгоритмами – в целом. Наиболее очевидной нерешенной задачей, безусловно, является устранение разрывов между верхними границами теорем 1, 2 и 3 и нижними границами теоремы 4. Также было бы любопытно посмотреть, насколько хорошо другие задачи оптимизации поддаются аппроксимации распределенным образом. В частности, распределенная сложность более общих классов линейных программ остается полностью открытым вопросом. Очень интригующей проблемой является определение необходимости рандомизации для получения эффективных по времени распределенных алгоритмов. В настоящее время лучшие детерминированные алгоритмы для нахождения доминирующего множества разумного размера и для многих других задач занимают время <math>2^{O(\sqrt{log \; n})}</math>, тогда как временная сложность лучших рандомизированных алгоритмов обычно является не более чем полилогарифмической от количества узлов. | ||
== См. также == | == См. также == |