Конспект: пределы приближения

Понятия

Схема приближения - для любого ε > 0 ответ не хуже (1 + ε) (для максимума - (1 − ε)) от оптимума. PTAS - время многочлен от n при каждом ε; FPTAS - многочлен и от n, и от 1/ε.

Сведение с разрывом - из NP-полного вопроса строится вход, где оптимум при «да» не больше a, а при «нет» больше α · a.

APX - задачи с приближением с постоянным множителем; APX-трудные - без PTAS, если P ≠ NP.

Теорема PCP - доказательство из NP проверяется чтением постоянного числа случайных символов; из неё выводятся тонкие пределы.

Что унести

РЮКЗАК: FPTAS
огрубить ценности: K = ε · vmax / n,  v' = ⌊v / K⌋;  веса точные
таблица «наименьший вес для огрублённой ценности»: n³ / ε
потеря < n · K = ε · vmax <= ε · OPT  (предметы, что не влезают, - вон)
12 предметов: ε = 0,5 - 139 столбцов, 99%;  ε = 0,2 - 359, оптимум
огрубить веса вниз: 166 при вместимости 120 - не помещается

PTAS И FPTAS
два сервера: k крупных перебором, остальные по списку
    гарантия 1 + 1/(k + 1), цена 2ᵏ
    6 задач: k = 0…4 - 41, k = 5 - 38, k = 6 - 37 = оптимум
FPTAS при ε < 1/OPT - точный псевдополиномиальный алгоритм
    ⇒ у сильно NP-трудных FPTAS нет (P ≠ NP)
раздача: фиксированное число серверов - FPTAS (Сахни);
         число серверов в условии - PTAS (Хохбаум, Шмойс), не FPTAS

РАЗРЫВ
коммивояжёр без метрики: 1 по рёбрам, α·n + 1 иначе
    гамильтонов цикл - n, нет - > α·n  ⇒ никакого множителя
    призма 6 против двудольного 30 (α = 2) и 126 (α = 10)
упаковка: разбиение → 2 контейнера или 3  ⇒ не лучше 3/2
    4 4 3 3 2 2: оптимум 2, «первый подходящий» 3
    для больших ответов: OPT + O(log OPT)

КАРТА ГРАНИЦ (при P ≠ NP)
MAX-3SAT по 3        7/8 монетка            7/8 + ε нельзя
покрытие множествами H(n) жадность          (1 − ε) ln n нельзя
k-центр              2                      2 − ε нельзя
вершинное покрытие   2                      √2 − ε нельзя;
                     2 − ε - если верна гипотеза об уникальных играх
метрический коммив.  1,5 − 10⁻³⁶            123/122 нельзя
упаковка             3/2                    3/2 − ε нельзя
H(n) − ln n → 0,577: жадность почти на пределе

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

Огрубил веса. Набор не помещается, а число на выходе выглядит лучше оптимума.

Взял vmax по предмету, который не влезает. Шаг огромный, всё огрубилось в ноль.

Искал FPTAS для сильно NP-трудной задачи. Её нет.

Взял PTAS с малым ε в продакшен. 2^(1/ε) при ε = 0,01 - это 2¹⁰⁰.

Свёл без разрыва и сделал вывод о приближении. Обычное сведение говорит только о точном ответе.

Искал множитель для коммивояжёра без метрики. Его нет ни при каком времени.

Улучшал жадность для покрытия множествами ради гарантии. Она уже на пределе.

Счёл предел вершинного покрытия закрытым. Между √2 и 2 - открытый вопрос.

Проверь себя

Почему в схеме для рюкзака огрубляют ценности, а не веса, и откуда потеря ε · OPT? Чем PTAS отличается от FPTAS и почему у сильно NP-трудных задач нет FPTAS? Построй сведение с разрывом для коммивояжёра без неравенства треугольника и для упаковки. Что утверждает теорема PCP? Где простые алгоритмы оказались лучшими возможными, а где граница ещё не найдена?

Понятия

Что унести

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

Проверь себя

Комментарии

Оставить комментарий