PTAS и FPTAS: точные схемы аппроксимации

PTAS и FPTAS: точные схемы аппроксимации

Семейство алгоритмов вместо одного

Обычный аппроксимационный алгоритм даёт фиксированную гарантию: например, 2-аппроксимация. Но что, если нам нужно точнее — скажем, 1.01-аппроксимация? PTAS (Polynomial-Time Approximation Scheme) — это не один алгоритм, а целое семейство алгоритмов Aε, параметризованное точностью ε > 0: Aε находит (1+ε)-аппроксимацию за полиномиальное время. Можно задать любую точность — цена: время растёт с убыванием ε.

PTAS: определение и примеры

Определение: алгоритм Aε — PTAS, если:

• Для любого ε > 0 алгоритм Aε находит (1+ε)-аппроксимацию
• Время работы полиномиально по n (размеру входа) при фиксированном ε

Важно: зависимость от ε может быть произвольной. Например, O(n^{1/ε}) — PTAS, но O(2^{1/ε}·n) — тоже PTAS.

Пример: задача о рюкзаке через PTAS

Идея: масштабируем ценности предметов.

1. Находим максимальную ценность cmax = max cᵢ
2. Масштабируем: c̃ᵢ = ⌊cᵢ · n/(ε · cmax)⌋ (округляем вниз)
3. Решаем ДП с масштабированными ценностями: время O(n · Σc̃ᵢ) = O(n · n²/ε) = O(n³/ε)
4. Возвращаем найденный набор предметов

Теорема: это (1+ε)-аппроксимация. Доказательство: потери от масштабирования ≤ ε · OPT/n за предмет, суммарно ≤ ε · OPT.

FPTAS: полиномиальная по 1/ε

Определение: алгоритм — FPTAS (Fully Polynomial-Time Approximation Scheme), если время полиномиально по n и по 1/ε.

Это гораздо сильнее PTAS: при ε = 0.01 (1% точность), время FPTAS = poly(n, 100), а PTAS = poly(n) но с константой e^{1/ε} или n^{1/ε}.

Задача о рюкзаке — FPTAS: масштабирование дает время O(n³/ε) = O(n² · n/ε) — полиномиально по n и 1/ε!

Задача расписания P||Cmax — FPTAS: FPTAS существует через аналогичное масштабирование времён.

Не все PTAS — FPTAS. Для evклидового TSP существует PTAS (алгоритм Арора), но FPTAS нет (TSP APX-трудна на общих метриках).

Почему TSP на произвольных метриках не имеет PTAS?

Для метрического TSP существует 3/2-аппроксимация (алгоритм Кристофидиса). Но PTAS нет!

Теорема: при P ≠ NP, метрический TSP не имеет (1+ε)-аппроксимации для любого ε > 0. (Предполагается, что для евклидова TSP PTAS есть — алгоритм Арора 1998.)

Доказательство: Если бы PTAS для TSP существовал, то Hamiltonian Cycle (гамильтоновский цикл) был бы решаем в полиномиальное время. Hamiltonian Cycle — NP-полная задача.

Конструкция: дан граф G = (V,E). Строим полный граф с весами dᵢⱼ = 1 если (i,j)∈E, иначе = n+1. Если G имеет гамильтоновский цикл → TSP-оптимум = n. Иначе → TSP-оптимум ≥ n+1 = (1+1/n)·n. Для ε < 1/n (1+ε)-аппроксимация отличила бы два случая → Hamiltonian Cycle решается. Противоречие!

Алгоритм Арора для евклидова TSP

Теорема (Ароre, 1998): для n точек в евклидовой плоскости, TSP имеет PTAS со временем O(n log^{O(1/ε)} n).

Ключевая идея: рандомизированное разбиение плоскости на квадраты и «порталы». Оптимальный маршрут, проходящий через порталы, аппроксимирует произвольный. ДП по квадрантам даёт точное решение для «портального» TSP.

PTAS для задач расписания

P||Cmax: n задач на m машинах. Минимизировать makespan (время до завершения всех задач).

LPT (Longest Processing Time First): 4/3-аппроксимация.

PTAS (Hochbaum-Shmoys, 1987): разделить на «длинные» (время > ε · OPT) и «короткие».

«Длинных» задач ≤ 1/ε → полный перебор их размещения за O((m+1)^{1/ε}) = O(m^{1/ε}) (экспоненциально по 1/ε, но полиномиально по n). «Короткие» добавляем жадно. (1+ε)-аппроксимация за O(n + m^{1/ε}).

Практическое значение: при ε = 0.1: время O(n + m^{10}). При n = 1000, m = 5: 5^{10} ≈ 10⁷ — за секунды! При ε = 0.01: 5^{100} ≈ 10^{70} — нереально. FPTAS нет для P||Cmax (APX-трудная).

Идея PTAS на примере рюкзака

PTAS для рюкзака основан на округлении и динамическом программировании:

1. Округлить ценности cᵢ' = ⌊cᵢ · K / c_max⌋ с подходящим K = ε · c_max / n
2. Решить округлённую задачу через DP по ценностям (а не по весам): O(n²·K) = O(n³/ε)
3. Гарантия: ALG ≥ (1−ε) · OPT

Это FPTAS — полиномиален и по n, и по 1/ε.

Метрический TSP и алгоритм Кристофидеса

Алгоритм Кристофидеса (1976) для метрического TSP даёт 1.5-аппроксимацию:

1. Построить минимальное остовное дерево T (MST)
2. Найти минимальное паросочетание M на вершинах с нечётной степенью в T
3. Соединить T ∪ M в эйлеров цикл
4. Сократить до гамильтонова цикла, пропуская повторные вершины

40 лет это была лучшая известная гарантия. В 2020 г. Карлин-Клайн-Гарасия-Гарбулевич улучшили до 1.5−10⁻³⁶ — крошечно, но эпохально.

Невозможность для общего TSP

Для не-метрического TSP (без неравенства треугольника) никакой константной аппроксимации не существует, если P ≠ NP. Доказательство: даже задача распознавания «существует ли гамильтонов цикл» NP-полна, и любой ρ-аппроксимационный алгоритм её бы решил.

Применения

PTAS используется в сетевом проектировании (k-MST, Steiner tree), календарном планировании (job shop scheduling), упаковке (Bin Packing — APTAS Карагианниса), геометрических задачах (евклидов TSP — PTAS Аroры).