Алгоритмы

Approximation Algorithms: Гарантированные приближения

Цели урока

Понимать approximation ratio
Реализовать 2-аппроксимацию для Vertex Cover
Понимать O(log n) для Set Cover
Знать аппроксимации для Metric TSP
Различать PTAS, FPTAS, APX

Предварительные знания

Жадные алгоритмы
Branch & Bound
Теория сложности

Когда точное решение невозможно за разумное время, approximation algorithms - спасение. Google использует их для routing, Amazon - для warehouse optimization, авиакомпании - для scheduling. Это практичный мост между теорией и реальностью.

Google Maps: approximation для routing
Scheduling: авиакомпании, фабрики
Network design: телеком
Advertising: allocation problems

Дэвид Джонсон и теория приближённых алгоритмов

Систематическая теория приближённых алгоритмов выросла из докторской диссертации Дэвида Джонсона в MIT и его статьи 1974 года 'Approximation Algorithms for Combinatorial Problems'. Джонсон ввёл идею гарантированного коэффициента приближения: алгоритм не находит оптимум, но доказуемо не хуже него в заданное число раз. Он же стал соавтором классической книги 1979 года 'Computers and Intractability' по NP-полноте вместе с Майклом Гэри. В 1990-х теорема PCP дала мощный инструмент для доказательства того, что для некоторых задач хорошее приближение само по себе NP-трудно, очертив границы возможного.

Зачем приближения?

**NP-hard задачи** не имеют известных полиномиальных точных алгоритмов. Но нам нужны решения! Варианты:

**Ключевая идея:** мы не знаем OPT, но можем доказать, что наше решение не хуже c×OPT.

**Факт:** для некоторых задач доказано, что лучше чем c-approximation невозможно за полиномиальное время (если P ≠ NP). Это важная граница.

Чем approximation algorithm лучше эвристики?

Approximation Ratio

**Approximation ratio (коэффициент аппроксимации)** - мера качества приближения.

**Классы аппроксимируемости:**

**Некоторые задачи не аппроксимируются!** Max-Clique не имеет n^(1-ε) аппроксимации (если P ≠ NP). Это фундаментальный барьер.

2-аппроксимация для минимизации означает:

Пример: Vertex Cover

**Vertex Cover:** найти минимальное множество вершин, покрывающее все рёбра графа.

**Доказательство 2-аппроксимации:**

**Unique Games Conjecture (UGC):** гипотеза, что 2-approximation для Vertex Cover оптимальна. Доказательство = миллион долларов.

Почему берём ОБЕ вершины ребра, а не одну?

Пример: Set Cover

**Set Cover:** покрыть универсум U минимальным числом множеств из коллекции S.

**Hardness:** Set Cover не имеет (1-ε)ln(n) аппроксимации если P ≠ NP. Жадный - оптимален!

Жадный Set Cover имеет ratio O(log n). Это:

Пример: Metric TSP

**TSP с неравенством треугольника:** dist(a,c) ≤ dist(a,b) + dist(b,c). Это позволяет аппроксимировать!

**Christofides Algorithm - 1.5-аппроксимация:**

**Для общего TSP** (без triangle inequality) нет константной аппроксимации! Можно доказать, что любой poly-time алгоритм может быть сколь угодно плох.

Почему общий TSP (без неравенства треугольника) не аппроксимируется?

PTAS и FPTAS

**PTAS (Polynomial Time Approximation Scheme):** для любого ε > 0 даёт (1+ε)-аппроксимацию.

**Иерархия:** FPTAS ⊂ PTAS ⊂ APX. Не все NP-hard задачи одинаково сложны для аппроксимации!

Чем FPTAS лучше PTAS?