Приближённые алгоритмы для NP-задач

Amazon доставляет 5 миллионов посылок в день. Оптимальная маршрутизация - NP-hard TSP. Точный алгоритм: недостижимо. Аппроксимация Кристофидеса: 1.5 * OPT, poly время. В реальности Amazon использует ещё более сложные комбинации алгоритмов. Но математическая гарантия качества - это фундамент, который аппроксимационная теория обеспечивает.

• **Amazon Logistics AMZL:** оптимизация маршрутов доставки через Vehicle Routing Problem (обобщение TSP). Используют комбинацию LP relaxation, локального поиска, аппроксимаций. Экономия в процентах от стоимости доставки = миллиарды долларов
• **Cloudflare PoP размещение:** выбор городов для Points of Presence через k-median / Facility Location (APX-hard). Жадные алгоритмы с LP lower bounds. 200+ PoP по всему миру оптимизированы через аппроксимации
• **Genome assembly (bioinformatics):** сборка генома из коротких reads = вариант Shortest Superstring (NP-hard). Используются 2-аппроксимации через overlap graphs. SPAdes, Velvet - популярные ассемблеры используют эти техники
• **VLSI layout (Intel, TSMC):** размещение элементов на чипе = вариант TSP/Quadratic Assignment (NP-hard). Simulated annealing + LP-based approaches. Качество размещения напрямую влияет на тактовую частоту

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

Алгоритм A является **ρ-аппроксимацией** для задачи минимизации если для любого входа x: A(x) ≤ ρ · OPT(x), где OPT(x) - оптимальное решение. Для максимизации: A(x) ≥ (1/ρ) · OPT(x). ρ ≥ 1 - чем ближе к 1, тем лучше. ρ = 1 - точный алгоритм.

**APX-hardness:** некоторые NP-задачи не допускают (1+ε)-аппроксимацию для любого ε > 0 (если P ≠ NP). Это называется APX-hard. TSP без треугольного неравенства APX-hard. MAX-SAT имеет 7/8-аппроксимацию (оптимальная по PCP theorem). **PCP theorem (1992)** - один из самых глубоких результатов: связывает аппроксимируемость с вероятностными доказательствами.

PTAS и FPTAS

**PTAS** (Polynomial Time Approximation Scheme): для любого ε > 0 существует poly-алгоритм с гарантией (1+ε). Время зависит от ε: может быть O(n^(1/ε)) или O(n^(2^(1/ε))). **FPTAS** (Fully Polynomial): время poly в n И в 1/ε. FPTAS мощнее и практичнее. Knapsack имеет FPTAS: O(n² / ε).

Трудность аппроксимации: PCP теорема

**PCP theorem (1992):** NP = PCP(log n, 1). Любое NP-доказательство можно перезаписать так, что верификатор проверяет только O(log n) случайных битов с вероятностью ошибки ≤ 1/2. Следствие - **зазоры в аппроксимируемости**: для MAX-SAT существует ε > 0 такое, что аппроксимация лучше (1-ε) невозможна (если P ≠ NP).

**Unique Games Conjecture (UGC, 2002)** Суброза Хота - гипотеза, из которой следуют оптимальные пределы аппроксимации для многих задач. Если UGC верна: Vertex Cover нельзя аппроксимировать лучше 2, MAX-CUT нельзя лучше 0.878..., Sparsest Cut нельзя лучше O(√log n). UGC объединяет трудность аппроксимации многих задач.

Приближённые алгоритмы на практике

В реальных системах часто используют **комбинацию** точных, приближённых и метаэвристических алгоритмов. Branch-and-bound с аппроксимационными нижними оценками (LP relaxation). Алгоритмы местного поиска (local search) с теоретическими гарантиями. Рандомизированные алгоритмы с анализом в среднем случае.

**LP relaxation + rounding** - общий приём: решаем линейную программу (LP) - полиномиально. Округляем дробное решение до целого - эвристически. Гарантия аппроксимации доказывается через integrality gap. Для Vertex Cover: LP даёт 2-аппроксимацию через LP duality. Для Set Cover: LP даёт ln(n)-аппроксимацию - та же граница что у жадного алгоритма.

Итоги

• **Коэффициент аппроксимации ρ:** алгоритм гарантирует решение не хуже ρ * OPT. Чем меньше ρ, тем лучше. ρ = 1 - точный алгоритм
• **PTAS vs FPTAS:** PTAS - poly для фиксированного ε. FPTAS - poly в n и 1/ε. Knapsack имеет FPTAS. TSP (Euclid) имеет PTAS но не FPTAS
• **PCP theorem:** устанавливает нижние границы аппроксимации. MAX-SAT: оптимум 7/8. MAX-CLIQUE: нет поли ρ-аппроксимации. Set Cover: оптимум ln(n)
• **На практике:** LP relaxation + rounding, жадные алгоритмы, локальный поиск. Гарантированное 'достаточно хорошее' решение за poly время

Связанные темы

Аппроксимация - практический ответ на NP-полноту:

• NP-полнота — Аппроксимационные алгоритмы - основной практический инструмент для NP-hard задач
• P vs NP — PCP theorem связывает аппроксимируемость с P vs NP: без poly алгоритма нет идеальной аппроксимации
• Рандомизированные алгоритмы — Рандомизация помогает в аппроксимации: MAX-SAT 7/8 достигается простым случайным присваиванием

Вопросы для размышления

• Алгоритм Кристофидеса для метрического TSP даёт 1.5-аппроксимацию. Karlin et al. (2021) улучшили до 1.5 - ε. Означает ли это шаг к точному poly-алгоритму для TSP?
• Greedy Set Cover оптимален по коэффициенту аппроксимации. Но для конкретных экземпляров задачи другой алгоритм может быть точнее. Как совместить теоретическую и практическую эффективность?
• FPTAS для Knapsack: при ε = 0.001 время O(n² * 1000) = O(n²) с большой константой. При каких n это практически применимо?

Связанные уроки

• comp-13-peg-packrat