Конспект раздела: что делать со сложной задачей

Одна мысль на весь раздел

NP-трудность закрывает одну дверь (если P ≠ NP, что не доказано) - точный ответ за многочлен на любом входе - и оставляет пять других. Каждая из них - отказ от одного требования: от точности (приближение), от гарантии (эвристика), от общности входов (параметр, структура), от полиномиального времени на малых входах (точный перебор и решатели), от знания будущего (онлайн). Выбор двери - инженерное решение, и у каждой есть доказанная цена и доказанный предел.

от чего отказываемся      что получаем                   предел
точность                  приближение с гарантией c      разрыв, PCP
гарантия                  эвристика, проверенная         нет: только
                          замером                        замер
общность входов           FPT по параметру, динамика     W[1], ETH
                          по разложению
полином на всех входах    точный ответ на малых и        экспонента
                          реальных входах                в худшем
знание будущего           конкурентное отношение         противник,
                                                         принцип Яо

В каталоге NP-полных задач пятый шаг назывался «выбрать плату», и вариантов было четыре. Вот где каждый разобран:

точный ответ на малых входах       точные методы: ветвление, части,
                                   ЦЛП- и SAT-решатели
приближённый с гарантией           приближения через нижнюю границу,
                                   ЛП-округление, схемы приближения
хороший без гарантии               локальный поиск, отжиг, табу,
                                   честный замер
точный на особом классе входов     параметр (FPT, ядро), малая
                                   древесная ширина, деревья

Дерево решений

задача NP-трудна
 ├─ вход мал или распадается на части?
 │     да → точно: ветвление с хорошим вектором, части отдельно,
 │          ЦЛП-решатель (сильная запись), SAT-решатель (CDCL)
 ├─ в задаче есть маленькое число (размер ответа, бюджет)?
 │     да → FPT? дерево поиска, ядро (покрытие - да; клика - W[1], нет)
 ├─ граф похож на дерево (малая древесная ширина)?
 │     да → динамика по мешкам, 2^O(w) · n
 ├─ нужна гарантия качества?
 │     ├─ есть нижняя граница по входу? → жадность с доказательством
 │     │      (раздача по списку, двойное дерево, самая дальняя точка)
 │     ├─ записывается ЦЛП? → округление релаксации,
 │     │      прямо-двойственный метод
 │     ├─ числа велики, задача слабо NP-трудна? → FPTAS
 │     └─ сначала проверить предел: разрыв, таблица PCP
 ├─ нужно просто хорошо и быстро?
 │     → старт жадностью, локальный поиск (2-opt), отжиг, табу;
 │       выбор - честным замером при равном бюджете
 └─ решения приходят по одному?
       → онлайн-правило с конкурентным отношением; монетка;
         прогноз с параметром доверия

Как части связаны

нижняя граница ──► гарантия приближения ──► разрыв ──► предел
 (средняя, МОД,       (2 − 1/m, 2, 2, 3/2)      (k-центр 2,
  свидетели,                                     покрытие ln n,
  релаксация,                                    MAX-3SAT 7/8)
  сумма плат)
релаксация ЛП ──► граница для ветвей и границ (точно)
              ──► округление (приближённо)
              ──► двойственная задача (прямо-двойственный метод)
              ──► половинки вершинного покрытия (ядро 2k)
ветвление ──► основа экспоненты = корень уравнения вектора
          ──► точные алгоритмы, FPT, DPLL
случайность ──► отжиг, перезапуски, случайное округление,
                цветное кодирование, кеш с пометками
динамика ──► таблица по огрублённым ценностям (FPTAS),
             по мешкам разложения, по наборам цветов

Числа раздела, которые стоит помнить

раздача задач: по списку 2 − 1/m,  по убыванию 4/3 − 1/(3m)
метрический коммивояжёр: двойное дерево 2, Кристофидес 3/2
k-центр: 2, лучше нельзя;  покрытие множеств: H(n) ≈ ln n, предел
вершинное покрытие: 2 (порог 1/2, прямо-двойственный), предел √2…2
MAX-SAT: монетка 1/2, округление 1 − 1/e, лучшее из двух 3/4
MAX-3SAT: 7/8 - предел;  упаковка: 3/2 - предел
рюкзак: FPTAS n³/ε;  раздача по многим серверам: PTAS, не FPTAS
ветвление: (1,1) 2, (1,2) 1,618, (1,3) 1,4656;  покрытие - 1,25284ᵏ
ядро покрытия: k² рёбер (Басс), 2k вершин (ЛП)
аренда лыж: 2 − 1/B, случайно e/(e − 1);  кеш: k, случайно 2Hₖ, Hₖ
список «в начало»: 2;  прогноз: 1 + λ и 1 + 1/λ
цветное кодирование: (2e)ᵏ;  плоские графы: 2^O(√n), не 2^o(√n)

Границы, общие для всех результатов

Все гарантии - про худший вход: на реальных данных алгоритм с гарантией 2 ошибается на проценты, а алгоритм без гарантии может быть лучше на конкретном входе. Все пределы условны: P ≠ NP, FPT ≠ W[1], ETH, SETH, гипотеза об уникальных играх. Неравенство треугольника, целые веса, малый параметр - условия, на которых держатся доказательства; без них гарантии исчезают молча.

Ловушки джокера

Сдался, увидев NP-трудность. Тридцать объектов решаются точно, тысяча с маленьким ответом - тоже.

Доказал гарантию на тестах. Худший вход среди случайных почти не встречается.

Забыл про неравенство треугольника. Двойное дерево и k-центр без него ничего не гарантируют.

Округлил релаксацию без доказательства. Порог зависит от задачи: 1/2, 1/f или случайный.

Огрубил веса вместо ценностей. Ответ не помещается.

Сравнил эвристики по лучшему прогону. Нужен равный бюджет, много зёрен и эталон.

Ветвился так, что ветка не тратит параметр. Глубина n вместо k.

Поверил модели без страховки. Без устойчивости прогноз хуже его отсутствия.

Искал алгоритм за пределом. Разрыв и таблица PCP показывают, где копать бесполезно.

Структура задачи задаёт гарантию

Задача	Инструмент	Условие или граница
MAX-CUT и терминальные разрезы	SDP и изолирующие разрезы	0,878 относится к нужной оптимальной релаксации; 2−2/k - к разделению всех k терминалов.
Дробная вершина релаксации	Отсечение Гомори	Сечение сохраняет целые решения и усиливает границу; направление границы зависит от min/max.
Малый набор удаляемых вершин	FVS и итеративное сжатие	Мера ограничивается функцией k; ветвление по длинному циклу этого не доказывает.
Ядро и ширина	Подсолнух, корона, Курсель	Проверяй эквивалентность редукции и зависимости от формулы и ширины.
Онлайн-решение	k-серверы и портфель	Метрика, делимость ресурса и комиссии определяют модель сравнения с офлайном.

Проверь, что можешь объяснить

Как доказать гарантию, не зная оптимума? Чем гарантия отличается от замера и почему хороший старт не обещает хорошего финиша? Когда точный ответ - законный выбор и что делает решатель с дробной релаксацией и с тупиком? Как округлить релаксацию для покрытия вершинами и множествами? Чем PTAS отличается от FPTAS и как разрыв доказывает невозможность приближения? Почему LRU k-конкурентен и что даёт монетка? Чем вершинное покрытие отличается от клики для параметризованного алгоритма? Почему динамика по мешкам платит экспонентой от ширины, а не от размера? Что запрещают ETH и SETH?