Локальные аппроксимации задач об упаковке и покрытии: различия между версиями

В работах [3, 4, 5] изучаются алгоритмы локальной аппроксимации для задач о покрытии и упаковке для графов, встречающихся в контексте беспроводных децентрализованных сетей и сетей датчиков. Из-за их масштаба, динамичности и ограниченности ресурсов такие сети представляют собой особенно интересную область для применения локальных распределенных алгоритмов.

'''Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (<math>1 + \varepsilon</math>)-аппроксимацию для поиска минимального доминирующего множества за время <math>O(log \; \Delta \; log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math>. Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (<math>1 + \varepsilon</math>)-аппроксимация может быть вычислена за <math>O(log^* (n) / \varepsilon + 1 / \varepsilon^{O(1)})</math> раундов.'''

Существует ряд открытых вопросов, связанных с распределенной аппроксимацией задач о покрытии и упаковке в частности и с алгоритмами распределенной аппроксимации – в целом. Наиболее очевидной нерешенной задачей, безусловно, является устранение разрывов между верхними границами теорем 1, 2 и 3 и нижними границами теоремы 4. Также было бы любопытно посмотреть, насколько хорошо другие задачи оптимизации поддаются аппроксимации распределенным образом. В частности, распределенная сложность более общих классов линейных программ остается полностью открытым вопросом. Очень интригующей проблемой является определение необходимости рандомизации для получения эффективных по времени распределенных алгоритмов. В настоящее время лучшие детерминированные алгоритмы для нахождения доминирующего множества разумного размера и для многих других задач занимают время <math>2^{O(\sqrt{log \; n})}</math>, тогда как временная сложность лучших рандомизированных алгоритмов обычно является не более чем полилогарифмической от количества узлов.