Теория аппроксимации: гарантии и границы

Хорошее решение вместо идеального

Если задача NP-трудная, мы не можем (предположительно) найти оптимальное решение за полиномиальное время. Но часто нам не нужна идеальная точность — достаточно «достаточно хорошего» решения. Аппроксимационные алгоритмы находят решения с гарантированным качеством: не более чем в ρ раз хуже оптимума. При ρ = 1.5 это означает «в полтора раза хуже оптимума» — для практических задач часто приемлемо. Теория аппроксимации изучает, насколько хорошо можно аппроксимировать NP-трудные задачи.

Коэффициент аппроксимации

Алгоритм A называется ρ-аппроксимационным (ρ ≥ 1), если для любого входа I:

max(A(I)/OPT(I), OPT(I)/A(I)) ≤ ρ

Для задач минимизации: A(I) ≤ ρ · OPT(I). Для максимизации: A(I) ≥ OPT(I)/ρ.

Примеры:

ρ = 1: точный алгоритм. Существует только для P-задач.
ρ = 2: решение не более чем вдвое хуже оптимума.
ρ = O(log n): логарифмическая аппроксимация (характерна для Set Cover).

Vertex Cover: 2-аппроксимация

Задача Vertex Cover: граф G = (V, E). Найти минимальное по размеру множество вершин C ⊆ V, такое что каждое ребро (u,v) имеет хотя бы один конец в C.

Жадный 2-аппроксимирующий алгоритм:

C = ∅, M = ∅ (M — паросочетание)
Пока существует ребро, не покрытое C:
- Выбрать произвольное непокрытое ребро (u,v)
- Добавить оба конца в C: C = C ∪ {u,v}
- Добавить ребро в M: M = M ∪ {(u,v)}
Вернуть C

Доказательство 2-аппроксимации: M — паросочетание (рёбра в M не имеют общих вершин). Следовательно, |M| ≤ OPT (оптимум должен покрыть все рёбра M → нужно ≥ |M| вершин). |C| = 2|M| ≤ 2 · OPT. ✓

Пример: K₄ (полный граф 4 вершины). OPT = 2 (любые 2 вершины покрывают все 6 рёбер? Нет: 2 вершины покрывают 5 рёбер. OPT = 3). Алгоритм выберет 2 ребра → 4 вершины. Аппроксимация = 4/3 < 2. ✓

APX-трудность и барьеры аппроксимации

APX-трудные задачи: нет PTAS (Polynomial-Time Approximation Scheme) при P ≠ NP.

Unique Games Conjecture (UGC, Хот 2002): строгая версия P ≠ NP. Если UGC верна:

Vertex Cover нельзя аппроксимировать лучше чем на (2−ε) при любом ε > 0
MAX-CUT нельзя аппроксимировать лучше чем на 0.878

Max-3-SAT: APX-трудная. Лучшая известная аппроксимация: 7/8 (рандомизированная — случайно назначаем каждую переменную). Невозможно лучше при P ≠ NP (Гастад 2001).

Bin Packing: анализ алгоритмов

Задача: n предметов с размерами sᵢ ∈ (0,1]. Минимальное число единичных корзин для размещения всех предметов.

First-Fit (FF): для каждого предмета кладём в первую корзину, куда помещается. Если нет — открываем новую. Аппроксимация: ≤ (17/10) OPT + 2 — не очень хорошо.

First-Fit Decreasing (FFD): сортируем предметы по убыванию, затем FF.

Теорема (Johnson, 1974): FFD(I) ≤ (11/9) OPT(I) + 4.

Как доказывается: анализируем, сколько «пространства» теряется в каждой корзине. При сортировке по убыванию потери минимальны.

FPTAS для Bin Packing: при заранее известных размерах существует (1+ε)-аппроксимация за O(n log n + f(1/ε)) — Fernandez de la Vega & Lueker (1981). Делим предметы на «большие» (sᵢ > ε) и «маленькие» (sᵢ ≤ ε), обрабатываем по-разному.

Полный разбор: метрическая задача о развёртке

Задача k-Median: даны n клиентов и n точек-«складов», метрика d. Выбрать k складов, минимизируя сумму расстояний клиентов до ближайшего склада.

Алгоритм Local Search (Arya et al., 2001): (3+ε)-аппроксимация.

Начальное решение: выбрать k произвольных складов S
Улучшение: для каждой замены (один склад из S на один вне S):
- Если замена уменьшает стоимость — делаем замену
Остановка: нет улучшающих замен (локальный оптимум)

Гарантия: в локальном оптимуме алгоритм даёт ≤ (3+ε) · OPT. Доказательство: амортизационный анализ замен. Применение: оптимальное размещение серверов, распределение региональных центров.

Классификация по гарантиям

Аппроксимационные алгоритмы делятся по силе гарантии:

Константная аппроксимация (ρ): ALG ≤ ρ · OPT для некоторого фиксированного ρ. Например, Vertex Cover — 2-аппроксимация (Бар-Йехуда, 1981).
Логарифмическая (O(log n)): Set Cover — ln n-аппроксимация через жадный (Йохансон, Ловаш, Чватал).
PTAS (Polynomial-Time Approximation Scheme): для любого ε > 0 существует алгоритм с гарантией (1+ε), полиномиальный по n (но возможно экспоненциальный по 1/ε).
FPTAS (Fully PTAS): полиномиальный и по n, и по 1/ε. Существует для рюкзака, не существует для TSP (если P ≠ NP).

Нижние границы аппроксимируемости

Многие задачи имеют доказанные пороги неаппроксимируемости (assuming P ≠ NP):

MAX-3SAT: нельзя аппроксимировать лучше 7/8 (Хостад, 1997)
Vertex Cover: нельзя лучше 1.36 (Динур-Сафра)
Set Cover: нельзя лучше (1−ε) ln n (Файге, Мошковиц)

Эти результаты получаются через PCP-теорему — одну из глубочайших теорем теории сложности.

Применения

Аппроксимационные алгоритмы критичны для больших данных, где даже B&B слишком медленен: рекомендательные системы (k-medoids, k-means через 2-аппроксимацию), социальные сети (influence maximization через жадный submodular алгоритм с гарантией 1−1/e), биоинформатика (выравнивание последовательностей).