PTAS и FPTAS: точность по заказу и кто её не допускает

Если ты отличишь PTAS от FPTAS по зависимости времени от ε, построишь схему для раздачи задач через точное размещение крупных и объяснишь, почему сильная NP-полнота запрещает FPTAS, листай до «Теперь сам».

Как думаешь, сколько стоит лишний знак точности

В первой главе раздача по убыванию гарантировала 4/3, а точного ответа там не было: задача о разбиении NP-трудна. В уроке о сортировке была обещана схема с точностью по заказу. Вот она: точно раскладываем k самых крупных задач, остальные раздаём жадно. Чем больше k, тем точнее.

Ответь себе до чтения: сколько стоит удвоить точность? Для рюкзака из прошлого урока - вдвое больше времени. Здесь - возвести время в квадрат: k растёт как 1/ε, а перебор крупных - как 2ᵏ. Обе схемы дают точность по заказу, но цена у них разного порядка. И у этого различия есть причина в самой задаче, а не в нашей изобретательности.

На что это похоже

Укладка багажа. Чемоданы раскладываешь вручную, перебирая варианты: их мало, и каждый важен. Мелочь рассовываешь не глядя: она не может сильно испортить итог, если чемоданы стоят правильно. Хочешь точнее - считаешь «чемоданами» больше вещей, и ручной работы становится больше, причём быстро: каждый новый чемодан удваивает число вариантов.

Схема для рюкзака устроена иначе: она не перебирает, а огрубляет, и огрубление дешевеет плавно. Различие между двумя рецептами - различие между PTAS и FPTAS.

Механизм: крупные точно, мелкие по списку

Схема для двух серверов. Отсортировать задачи по убыванию. Первые k разложить по двум серверам перебором 2ᵏ вариантов, выбрав лучший. Остальные класть по одной на менее загруженный сервер.

Гарантия. Если позже всех закончилась крупная задача, расписание совпадает с наилучшим для крупных, а оно не хуже OPT. Если мелкая задача ℓ - как в первой главе, T ≤ P/2 + p_ℓ / 2. Задача ℓ не длиннее (k + 1)-й по величине, а k + 1 задач не короче её дают OPT ≥ (k + 1) · p_ℓ / 2. Значит, p_ℓ / 2 ≤ OPT / (k + 1) и T ≤ (1 + 1/(k + 1)) · OPT.

Два вида схем. Для точности ε нужно k = ⌈1/ε⌉ − 1, время 2^(1/ε) · n log n. При фиксированном ε - многочлен от n: это PTAS (polynomial-time approximation scheme). Время как многочлен и от n, и от 1/ε - FPTAS, как у рюкзака. Для двух и любого другого фиксированного числа серверов FPTAS тоже есть (Сахни, 1976): там задача, как рюкзак, сдаётся таблице при малых числах. Если число серверов входит в условие, PTAS остаётся (Хохбаум, Шмойс, 1987), а FPTAS - нет.

Почему FPTAS нет. Раздача задач по произвольному числу серверов сильно NP-полна: остаётся трудной, даже когда длительности не больше многочлена от n. Пусть есть FPTAS. Длины целые, значит, OPT целое и не больше суммы длин P. Возьмём ε = 1/(P + 1): ответ не хуже (1 + ε) · OPT < OPT + 1, то есть ровно OPT. Время - многочлен от n и P. Для входов с малыми числами это точный полиномиальный алгоритм для NP-трудной задачи - значит, P = NP. Тот же довод работает для любой сильно NP-трудной задачи с целой целью, ограниченной многочленом.

Правило

PTAS - схема, время которой полиномиально по n при каждом фиксированном ε; FPTAS - полиномиально и по n, и по 1/ε. Раздача задач: k крупных точно, остальные по списку, гарантия 1 + 1/(k + 1) - это PTAS. У сильно NP-трудных задач с целой целью FPTAS нет, если P ≠ NP: с ε < 1/OPT она стала бы точным псевдополиномиальным алгоритмом.

Разбор: шесть задач, растущее k

optimum_dvuh - точный ответ таблицей достижимых сумм. shema(zadachi, k) - перебор k крупных и раздача остальных. Печать: k, число вариантов перебора, ответ, отношение к оптимуму, гарантия.

def optimum_dvuh(zadachi):
    vsego = sum(zadachi)
    dostizhimo = [False] * (vsego + 1)
    dostizhimo[0] = True
    for p in zadachi:
        for s in range(vsego, p - 1, -1):
            if dostizhimo[s - p]:
                dostizhimo[s] = True
    s = vsego // 2
    while not dostizhimo[s]:
        s = s - 1
    return vsego - s

def shema(zadachi, k):
    po_ubyvaniyu = sorted(zadachi, reverse=True)
    krupnye = po_ubyvaniyu[:k]
    luchshee = [sum(krupnye), 0]
    for maska in range(2 ** len(krupnye)):
        a = 0
        b = 0
        for i in range(len(krupnye)):
            if maska >> i & 1 == 1:
                a = a + krupnye[i]
            else:
                b = b + krupnye[i]
        if max(a, b) < max(luchshee):
            luchshee = [a, b]
    nagruzka = luchshee
    for p in po_ubyvaniyu[k:]:
        if nagruzka[0] <= nagruzka[1]:
            nagruzka = [nagruzka[0] + p, nagruzka[1]]
        else:
            nagruzka = [nagruzka[0], nagruzka[1] + p]
    return max(nagruzka)

zadachi = [15, 10, 20, 16, 11, 2]
opt = optimum_dvuh(zadachi)
print(opt)
for k in range(7):
    otvet = shema(zadachi, k)
    garantiya = round(1 + 1 / (k + 1), 4)
    print(k, 2 ** k, otvet, round(otvet / opt, 4), garantiya)

37
0 1 41 1.1081 2.0
1 2 41 1.1081 1.5
2 4 41 1.1081 1.3333
3 8 41 1.1081 1.25
4 16 41 1.1081 1.2
5 32 38 1.027 1.1667
6 64 37 1.0 1.1429

Оптимум 37: 20 + 15 + 2 и 16 + 11 + 10. При k = 0 схема - это раздача по убыванию из первой главы: 41. До k = 4 ничего не меняется: ошибка сидит в том, куда легла задача 10, а она пятая по величине. При k = 5 перебор захватил и её - ответ 38. При k = 6 перебирается всё - оптимум.

Гарантия в последнем столбце - худший случай: она убывает как 1 + 1/(k + 1), а цена растёт как 2ᵏ. При малых k она хуже настоящей гарантии сортировки (7/6 для двух серверов) - общая оценка грубее специальной. Но только общая оценка позволяет заказать любую точность.

Разбор: FPTAS с точностью меньше 1/OPT

Рюкзак из восьми предметов и схема из прошлого урока, которая теперь возвращает ширину таблицы и настоящую ценность набора. Последняя точность - 1/(OPT + 1).

def tochno(cennosti, vesa, W):
    luchshee = [0] * (W + 1)
    for i in range(len(vesa)):
        for w in range(W, vesa[i] - 1, -1):
            if luchshee[w - vesa[i]] + cennosti[i] > luchshee[w]:
                luchshee[w] = luchshee[w - vesa[i]] + cennosti[i]
    return luchshee[W]

def shema(cennosti, vesa, W, eps):
    n = len(cennosti)
    K = eps * max(cennosti) / n
    grubo = []
    for c in cennosti:
        grubo.append(int(c // K))
    vsego = sum(grubo)
    legchajshij = [sum(vesa) + 1] * (vsego + 1)
    cennost = [0] * (vsego + 1)
    legchajshij[0] = 0
    for i in range(n):
        for s in range(vsego, grubo[i] - 1, -1):
            ves = legchajshij[s - grubo[i]] + vesa[i]
            if ves < legchajshij[s]:
                legchajshij[s] = ves
                cennost[s] = cennost[s - grubo[i]] + cennosti[i]
    s = vsego
    while legchajshij[s] > W:
        s = s - 1
    return [vsego, cennost[s]]

cennosti = [23, 10, 2, 15, 6, 6, 9, 15]
vesa = [5, 13, 16, 15, 22, 15, 12, 6]
W = 50
opt = tochno(cennosti, vesa, W)
print(opt)
for eps in [0.9, 0.5, 0.2, 1 / (opt + 1)]:
    print(round(eps, 4), shema(cennosti, vesa, W, eps))

63
0.9 [28, 62]
0.5 [57, 62]
0.2 [146, 63]
0.0156 [1910, 63]

При ε = 0,9 и 0,5 схема промахнулась на единицу: 62 при оптимуме 63, в пределах гарантии. При ε = 1/64 гарантия «не хуже (1 − ε) · OPT» означает «хуже не больше чем на 63/64 < 1» - а ценности целые, так что ответ обязан быть точным. Он и точный. Цена - таблица в 1910 столбцов, и она растёт пропорционально оптимуму: это обычная псевдополиномиальная таблица, только полученная другой дорогой.

Для рюкзака это нестрашно: псевдополиномиальный алгоритм у него и так есть. Но для сильно NP-трудной задачи - раздачи задач по произвольному числу серверов, упаковки в контейнеры, коммивояжёра - такой алгоритм означал бы P = NP. Поэтому у них в лучшем случае PTAS, где время экспоненциально по 1/ε.

Что ломается без этого

Ищут FPTAS для сильно NP-трудной задачи. Её нет, если P ≠ NP. Время, полиномиальное по 1/ε, бывает только у задач, которые сдаются таблице при малых числах.

Берут PTAS с малым ε в продакшен. 2^(1/ε) при ε = 0,01 - это 2¹⁰⁰. PTAS часто теоретическая: она доказывает, что точность заказать можно, но заказывать её дорого.

Путают «схему» с эвристикой. Схема гарантирует 1 + ε для любого входа; эвристика вроде отжига обещает только «обычно хорошо».

Зачем это в работе

Когда заказчик спрашивает «а можно точнее?», ответ зависит от вида задачи. Рюкзак, бюджет, загрузка одним ресурсом, раздача на два-три сервера - да, и почти даром: FPTAS. Раздача на сколько угодно серверов - да, но дорого: PTAS, где каждый знак точности умножает время. Упаковка - только асимптотически: лишних контейнеров сверх оптимума можно сделать сколь угодно малую долю, но абсолютной схемы нет. Коммивояжёр без неравенства треугольника, k-центр - нет вовсе: ниже определённого множителяРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: Разрыв: почему некоторые задачи нельзя приблизить не опуститься никаким временем, если P ≠ NP. Различать эти три ответа - значит не обещать невозможного.

Теперь сам

1. Схема для двух серверов при k = 9. Какова гарантия и сколько вариантов перебирается?
2. Почему для рюкзака FPTAS с ε = 1/(OPT + 1) не противоречит NP-полноте?
3. Задача сильно NP-трудна, цель целая и не больше n². Может ли у неё быть PTAS? А FPTAS?