Конспект: приближённые алгоритмы и нижние границы

Понятия

c-приближённый алгоритм - для любого входа ответ не хуже оптимума в c раз (для минимума: ответ ≤ c · OPT). c - граница худшего случая, а не типичная ошибка.

Нижняя граница оптимума - число, видное по входу, которого оптимум точно не меньше. Через неё доказывают гарантию: оптимум знать не нужно.

Неравенство треугольника - d(a, c) ≤ d(a, b) + d(b, c): напрямую не длиннее, чем через третью точку. На нём держатся срезки в маршрутах и пары у одного центра.

Доминирующее множество - вершины, такие, что каждая вершина графа в наборе или рядом с ним. NP-полно.

Что унести

ДОКАЗАТЕЛЬСТВО ГАРАНТИИ - ТРИ ХОДА
1. найти по входу нижнюю границу L <= OPT
2. разложить ответ на части
3. каждую часть оценить через L
итог: ответ <= c · L <= c · OPT
бонус: L можно напечатать рядом с ответом - это сертификат

РАЗДАЧА ЗАДАЧ ПО m СЕРВЕРАМ
границы:   OPT >= P / m  (средняя),   OPT >= max p  (самая длинная)
по приходу, на самый свободный:     2 − 1/m      (Грэм, 1966)
    худший вход: m(m − 1) единиц, потом одна задача длины m
по убыванию, на самый свободный:    4/3 − 1/(3m) (Грэм, 1969)
    довод на 3/2: первые m + 1 задач не короче последней,
    две из них в оптимуме вместе, значит p_last <= OPT / 2
    худший вход: по две задачи 2m−1 … m+1 и три задачи m
семь задач 3 7 5 3 1 9 1, три сервера:
    по приходу 15, по убыванию 10, граница 10, оптимум 10
40 случайных входов, 2 сервера:  средняя ошибка 6,2% и 0,9%

МЕТРИЧЕСКИЙ КОММИВОЯЖЁР
граница:  вес МОД <= OPT  (маршрут без ребра - остов)
двойное дерево: прямой порядок обхода МОД      <= 2 · OPT
Кристофидес: МОД + паросочетание нечётных
             вершин + эйлеров цикл + срезки     <= 3/2 · OPT
             2020: 3/2 − 10⁻³⁶ (Карлин, Кляйн, Овейс Гарен)
восемь точек: МОД 24,14, маршрут 40,87, оптимум 32,23
нет неравенства треугольника: 204 против 8, гарантии нет;
    если город можно проезжать дважды - заменить расстояния
    кратчайшими путями (Флойд-Уоршелл)

k-ЦЕНТР
самая дальняя точка (Гонсалес):   радиус <= 2 · OPT
свидетели: k центров + самая дальняя точка, попарно >= r
           две у одного центра в оптимуме  →  OPT >= r / 2
12 магазинов, 3 склада:  радиус 9, граница 4,5, оптимум 5,831
лучше 2 нельзя при P ≠ NP:
    расстояния 1 (ребро) и 2 (нет ребра) - радиус 1 или 2;
    радиус 1 = доминирующее множество

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

Доказал гарантию на тестах. Сто случайных входов не содержат худшего: мелочь, потом одна длинная задача, на случайных данных не выпадает, а в ночной очереди - обычное дело.

Взял одну границу из двух. Средняя не видит огромной задачи, самая длинная не видит тысячи мелких.

Сравнил с оптимумом, которого не посчитать. В отчёт идёт граница, а не «примерно оптимум».

Отсортировал задачи, которые приходят потоком. Сортировка требует знать всё заранее.

Поверил метрике, не проверив. Тарифы, пробки, пересадки ломают неравенство треугольника, а с ним всю гарантию.

Счёл гарантию типичной ошибкой. Гарантия 2, а на деле 20-40% - и наоборот, гарантия 7/6 не защищает от ошибки на другом входе.

Искал множитель меньше двух для k-центра. При P ≠ NP его нет.

Проверь себя

Найди нижнюю границу для раздачи задач 6, 2, 8, 4, 5, 9 по трём серверам. Почему в гарантии раздачи по приходу стоит 2 − 1/m, а не просто 2? Откуда в доводе о сортировке берётся m + 1 задача? Почему вес остовного дерева не больше длины маршрута и где в двойном дереве нужно неравенство треугольника? Как выбор самой дальней точки сам предъявляет нижнюю границу? Почему расстояния 1 и 2 запрещают множитель меньше двух?