Конспект: ЛП-округление и прямо-двойственный метод

Понятия

ЛП-округление - решить релаксацию и превратить дробный ответ в целый с доказанной потерей.

Разрыв целочисленности - наибольшее отношение целого оптимума к оптимуму релаксации. Через эту релаксацию гарантию лучше разрыва не доказать.

f в покрытии множествами - наибольшее число множеств, содержащих один элемент. Для вершинного покрытия f = 2.

MAX-SAT - выполнить как можно больше скобок. Метод условных ожиданий - фиксировать переменные по одной так, чтобы ожидание не падало.

Прямо-двойственный метод - строить допустимое решение двойственной задачи и по тесным ограничениям собирать ответ.

Что унести

ВЕРШИННОЕ ПОКРЫТИЕ С ВЕСАМИ
«оба конца ребра»: гарантии нет (звезда: 6 против 1)
релаксация: min Σ w·x,  x_u + x_v >= 1,  0 <= x <= 1
    есть оптимум из 0, 1/2, 1 (Немхаузер, Троттер)
порог 1/2: покрытие, цена <= 2 · LP <= 2 · OPT
граф из 7 вершин: LP 26,5 → округление 53, оптимум 28
полный граф K_n: LP n/2, целый n − 1, разрыв 2 − 2/n

ПОКРЫТИЕ МНОЖЕСТВАМИ
порог 1/f: цена <= f · LP
случайное: каждое множество с вероятностью x_j, раунды
    P(элемент не накрыт за раунд) <= e^(−1)
    2 ln n раундов: всё накрыто с вероятностью >= 1 − 1/n,
    цена <= 2 ln n · LP в ожидании
12 элементов, f = 3: LP 22,33, порог 44, случайно 26-37,
    жадность 23 = оптимум

MAX-SAT
монетка: скобка длины k  1 − 2⁻ᵏ        (1/2, 3/4, 7/8, …)
округление y: >= (1 − (1 − 1/k)ᵏ) · z    (1, 0,75, 0,704, … → 0,632)
лучшее из двух: >= 3/4 · LP >= 3/4 · OPT
    (наименьшее среднее - 0,75 на длинах 1 и 2)
18 скобок: оптимум 16, LP 16,67, монетка 12,62, округление 15,37;
    условные ожидания из обоих стартов - 16

ПРЯМО-ДВОЙСТВЕННЫЙ МЕТОД
двойственная: max Σ y_e,  Σ y_e у вершины <= w_v
проход: y = min(остаток[u], остаток[v]); остатки − y
покрытие = вершины с остатком 0;   цена <= 2 · Σ y <= 2 · OPT
Σ y - нижняя граница по этому входу
граф из 7 вершин: прямой порядок 39 (граница 23), после чистки 30;
    обратный - 28 (граница 17)
чистка: выбрасывать лишние, начиная с тяжёлых

Ловушки джокера

Взял «оба конца» для весов. Переплата во сколько угодно раз.

Округлил «до ближайшего». Две половинки на ребре округлятся вниз - ребро не покрыто.

Перенёс порог 1/2 на множества. Нужен 1/f.

Сделал один раунд случайного округления. Каждый элемент пуст с вероятностью до 37%.

Взял одну монетку или одно округление для MAX-SAT. Каждый способ проваливается на своих скобках.

Выдал случайный ответ без дерандомизации. Ожидание - не гарантия конкретного броска.

Позволил ребру платить больше остатка. Граница становится враньём.

Не почистил ответ. На треть дороже без причины.

Проверь себя

Почему порог 1/2 даёт покрытие и почему оно не дороже двух LP? Что такое разрыв целочисленности и чему он равен на полном графе? Почему порог для множеств - 1/f, и откуда ln n у случайного округления? Посчитай вероятности монетки и округления для скобки длины 3. Проведи прямо-двойственный метод на треугольнике с весами 2, 3, 4 и назови границу.

SDP MAX-CUT заменяет знаки единичными векторами; случайная гиперплоскость режет пару с вероятностью θ/π. Ожидаемая гарантия Гоэманса-Уильямсона ≥ 0,878·OPT требует оптимизации релаксации и неотрицательных весов.

Multiway cut разделяет все терминалы. Минимальные изолирующие разрезы, кроме самого дорогого, дают (2 − 2/k)-приближение; ЛП помещает метки в симплекс.