Аппроксимация и inapproximability

UPS ежедневно экономит миллионы долларов, используя аппроксимационные алгоритмы для маршрутизации. Точное решение TSP для 21 миллиона посылок физически невозможно вычислить, но алгоритм Christofides гарантирует маршрут не хуже 1.5 от оптимального. Аппроксимационные алгоритмы - это не компромисс. Это наука о том, как много можно получить полиномиально.

• **UPS ORION** (On-Road Integrated Optimization and Navigation) использует аппроксимационные алгоритмы для маршрутизации 55 000 водителей - экономия 10 млн галлонов топлива в год
• **VLSI-дизайн** использует алгоритмы аппроксимации для задачи размещения и разводки чипов: точное решение NP-трудно, но аппроксимации с гарантией качества достаточны для production
• **Задача расписания** в кластерных вычислениях (распределение задач по серверам) решается PTAS-алгоритмами с гарантированным отклонением от оптимального makespan

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

UPS ежедневно маршрутизирует 21 миллион посылок. Оптимальный маршрут - это задача коммивояжёра (TSP), NP-трудная. Точного решения нет - но хорошей аппроксимации достаточно: алгоритм Christofides даёт маршрут длиной не более чем в 1.5 раза хуже оптимального. Это и есть **коэффициент аппроксимации alpha**: отношение стоимости найденного решения к оптимальному. Для задачи минимизации alpha >= 1 (нашли не дороже чем alpha * OPT). Для максимизации alpha <= 1 (нашли не хуже чем alpha * OPT).

Аппроксимационный алгоритм гарантирует коэффициент на всех входах, не только в среднем. Классические результаты: Vertex Cover имеет 2-аппроксимацию (жадный алгоритм); Set Cover - O(log n)-аппроксимацию (тоже жадный); TSP с метрическим ограничением - 1.5-аппроксимацию (Christofides, 1976). В 2021 году Karlin, Klein, Gharan улучшили Christofides до 1.5-epsilon для metrical TSP.

PTAS: Polynomial-Time Approximation Scheme

Фиксированный коэффициент 1.5 или 2 - часто достаточно. Но иногда нужна произвольно точная аппроксимация. **PTAS (Polynomial-Time Approximation Scheme)** - семейство алгоритмов A_epsilon, которое при любом epsilon > 0 находит решение с коэффициентом (1+epsilon) за полиномиальное (по n) время. Формально: для каждого фиксированного epsilon алгоритм работает за poly(n), но показатель полинома может зависеть от epsilon. Задача Knapsack имеет PTAS с временем O(n^2 / epsilon) - для epsilon=0.01 получаем решение не хуже 1% от оптимума.

PTAS существуют для многих геометрических задач: Euclidean TSP (Arora, 1998 - O(n log n) для любого epsilon), Euclidean Steiner Tree, k-means clustering. Для комбинаторных задач PTAS реже: Knapsack, Bin Packing имеют PTAS. Метрическое TSP имеет только 1.5-аппроксимацию (не PTAS) - нет PTAS если P != NP по Papadimitriou-Vempala.

FPTAS: Fully Polynomial-Time Approximation Scheme

PTAS с временем O(n^(1/epsilon)) или O(2^(1/epsilon) * n) практически бесполезен при epsilon = 0.001 - показатель экспоненциально вырастает. **FPTAS** устраняет этот недостаток: время работы полиномиально по обоим параметрам - n и 1/epsilon. Формально: O(poly(n, 1/epsilon)). Knapsack имеет FPTAS с временем O(n^2 / epsilon) - при n=1000 и epsilon=0.001 это 10^12 операций, что уже граничит с практичностью. Задача Subset Sum также имеет FPTAS. FPTAS является более сильным понятием, чем PTAS.

FPTAS -> PTAS, но не наоборот. Если задача NP-трудна в счётном смысле (strongly NP-hard), то FPTAS не существует если P != NP. TSP, 3-Colorability - strongly NP-hard, поэтому не имеют FPTAS. Knapsack - weakly NP-hard (NP-трудность исчезает при унарном кодировании), поэтому FPTAS возможен. Это математически элегантное разграничение: weakly NP-hard = FPTAS может существовать.

Unique Games Conjecture и пределы аппроксимации

2002 год, Subhash Khot формулирует **Unique Games Conjecture (UGC)**: задача Unique Label Cover NP-трудна даже в режиме аппроксимации. Это гипотеза - не теорема - но она перевернула теорию аппроксимации. Из UGC следуют точные нижние границы: Max-Cut не может быть аппроксимирован лучше коэффициента 0.878... (ровно то, что даёт алгоритм Goemans-Williamson!), Vertex Cover нельзя аппроксимировать лучше 2-epsilon. Иными словами: десятилетние «лучшие известные» алгоритмы оказались оптимальными при UGC.

Khot, Kindler, Mossel, O'Donnell (2007) доказали, что из UGC следует оптимальность SDP-аппроксимации для Max-Cut. Prasad Raghavendra (2008) показал, что для широкого класса задач CSP SDP-аппроксимация оптимальна при UGC. UGC эквивалентен утверждению, что SDP-relaxation - правильный инструмент для всех «симметричных» задач оптимизации. UGC остаётся открытой проблемой: Subhash Khot получил премию Невана (Fields-аналог для CS) в 2014 году.

Ключевые идеи

• **Коэффициент аппроксимации** = ALG/OPT (минимизация) или OPT/ALG (максимизация); гарантируется на всех входах, не только в среднем
• **PTAS** даёт (1+epsilon)-аппроксимацию за poly(n) для любого фиксированного epsilon; **FPTAS** - за poly(n, 1/epsilon); strongly NP-hard задачи не имеют FPTAS
• **UGC** задаёт точные нижние границы аппроксимируемости: алгоритм Goemans-Williamson (0.878 для Max-Cut) оптимален при UGC

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

Аппроксимация строится поверх NP-теории и связана с рандомизированными алгоритмами:

• NP и NP-полнота — Аппроксимационные алгоритмы нужны именно для NP-трудных задач; inapproximability доказывается через NP-трудность gap-версий
• Parameterized Complexity — Альтернативный подход к NP-трудным задачам: FPT-алгоритмы дают точное решение за f(k)*poly(n), а не аппроксимацию

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

• Vertex Cover имеет 2-аппроксимацию, но UGC предсказывает, что лучше 2-epsilon невозможно. Означает ли это, что жадный алгоритм для Vertex Cover является 'правильным' решением задачи?
• Задача k-means clustering NP-трудна, но PTAS существует. Почему на практике используют алгоритм Ллойда без теоретических гарантий - и насколько это оправдано?
• PCP-теорема показывает, что NP-трудность и inapproximability тесно связаны. Что это говорит о природе вычислительной сложности - является ли аппроксимационная сложность 'отдельной' теорией или частью той же теории?

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

• alg-34-approximation