4430
правок
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Материал из WEGA
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 18:05, 27 августа 2021
, 27 августа 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
'''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) | '''Теорема 6. На сети BIG можно найти константные аппроксимации для вычисления минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) детерминированным образом за <math>O(log \; \Delta \cdot log^* n)</math> раундов.''' | ||
