4430
правок
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Материал из WEGA
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 19:28, 19 июня 2021
, 19 июня 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 51: | Строка 51: | ||
Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером | Алгоритм, на котором основывается теорема 1, требует использования только небольших сообщений размером <math>O(log(\rho \Delta))</math> и чрезвычайно простых и эффективных локальных вычислений. Если допустить большие сообщения и более сложные (но все еще полиномиальные) локальные вычисления, то результат теоремы 1 можно улучшить: | ||
Теорема 2. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом O( | '''Теорема 2. За k раундов алгоритмы (P) и (D) могут быть аппроксимированы с коэффициентом <math>O(n^{O(1/k)})</math>. Таким образом, константная аппроксимация может быть найдена за время O(log n).''' | ||
| Строка 60: | Строка 60: | ||
Теорема 3. Пусть | '''Теорема 3. Пусть <math>\Delta</math> – максимальная степень заданного графа сети. За k раундов минимальное доминирующее множество может быть аппроксимировано с коэффициентом <math>O(\Delta^{O(1 / \sqrt{k})})</math> с ожидаемым размером используемых сообщений <math>O(\Delta)</math>. Без ограничения на размер сообщения может быть достигнут ожидаемый коэффициент аппроксимации <math>O(n^{O(1/k)} \cdot log \; \Delta)</math>. Задачи о минимальном вершинном покрытии и максимальном паросочетании могут быть аппроксимированы за k раундов с коэффициентом <math>O(\Delta^{1/k})</math>.''' | ||
