4430
правок
Локальные аппроксимации задач об упаковке и покрытии: различия между версиями
Материал из WEGA
Локальные аппроксимации задач об упаковке и покрытии (посмотреть исходный код)
Версия от 19:32, 19 июня 2021
, 19 июня 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами | Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами <math>\Omega(\Delta^{1/k} / 1)</math> и <math>\Omega(n^{\Omega(1 / k^2)} / k)</math>. Это подразумевает нижние временные границы <math>\Omega(log \; \Delta / log \; log \; \Delta)</math> и <math>\Omega(\sqrt{log \; n / log \; log \; n})</math> для константных или даже полилогарифмических коэффициентов аппроксимации. Те же границы справедливы для задач о минимальном доминирующем множестве и о максимальном паросочетании, а также для лежащих в их основе LP. | ||
