Прямо-двойственный метод: рёбра платят за вершины

Если ты запишешь двойственную задачу к вершинному покрытию, объяснишь, почему сумма плат рёбер - нижняя граница, и докажешь, что оплаченные вершины стоят не больше двух таких сумм, листай до «Теперь сам».

Как думаешь, можно ли без решателя

Прошлые уроки начинались одинаково: решить релаксацию, потом округлить. Для графа на миллион вершин и десять миллионов рёбер это отдельный проект: решатель ЛП, память, время. А гарантия у округления по порогу всего лишь 2.

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

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

Скидываемся на камеры. Каждая улица (ребро) хочет, чтобы хотя бы один из её перекрёстков был под камерой, и готова вложиться. Камера на перекрёстке стоит столько-то; улица вкладывает деньги в оба своих перекрёстка сразу. Как только на каком-то перекрёстке набрана полная цена камеры, её ставят - и все улицы через этот перекрёсток уже под наблюдением, вкладываться им больше незачем.

Сколько всего вложили улицы? Ни один перекрёсток не получил больше цены камеры - это и есть «допустимое решение двойственной задачи», а значит, нижняя граница. А сколько заплатили за камеры? Каждая камера оплачена улицами полностью, и каждая улица вкладывала не больше чем в два перекрёстка.

Механизм: пара задач и один проход

Пара задач. Прямая - релаксация покрытия; двойственная - плата y_e за каждое ребро:

прямая:        min Σ w_v · x_v,   x_u + x_v >= 1,   x >= 0
двойственная:  max Σ y_e,         Σ y_e (по рёбрам у v) <= w_v,  y >= 0

Из раздела о линейном программировании: значение любого допустимого решения двойственной задачи не больше значения любого допустимого решения прямой (слабая двойственность). Значит, любая допустимая расстановка плат даёт Σ y_e ≤ LP ≤ OPT - нижнюю границу, которую можно предъявить.

Метод (Бар-Иегуда, Эвен, 1981).

остаток[v] = w_v для всех вершин
для каждого ребра u-v:
    y = min(остаток[u], остаток[v])      ребро платит, сколько может
    остаток[u] −= y;  остаток[v] −= y
покрытие = вершины с остатком 0          «оплаченные»

Почему покрытие. После обработки ребра у одного из его концов остаток 0 - этот конец в покрытии.

Почему не больше двух оптимумов. Оплаченная вершина стоит ровно сумму плат её рёбер. Сложим по вершинам покрытия: каждая плата y_e попадёт в сумму не больше двух раз - по разу за каждый конец. Получается цена покрытия ≤ 2 · Σ y_e ≤ 2 · OPT.

Правило

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

Разбор: тот же граф с весами

Граф из семи вершин из урока об округлении по порогу: релаксация 26,5, оптимум 28. Рёбра в порядке записи.

def pryamo_dvojstvenno(ves, rebra):
    ostatok = ves[:]
    plata = []
    for r in rebra:
        u = r[0]
        v = r[1]
        if ostatok[u] == 0 or ostatok[v] == 0:
            plata.append(0)
        else:
            y = min(ostatok[u], ostatok[v])
            ostatok[u] = ostatok[u] - y
            ostatok[v] = ostatok[v] - y
            plata.append(y)
    pokrytie = []
    for v in range(len(ves)):
        if ostatok[v] == 0:
            pokrytie.append(v)
    return [pokrytie, plata]

ves = [7, 9, 6, 9, 8, 9, 5]
rebra = [[0, 4], [0, 6], [1, 2], [1, 4], [1, 5], [2, 4], [2, 6],
         [3, 5], [5, 6]]
p = pryamo_dvojstvenno(ves, rebra)
cena = 0
for v in p[0]:
    cena = cena + ves[v]
print(p[0], cena)
print(p[1], sum(p[1]), round(cena / sum(p[1]), 3))

[0, 1, 2, 4, 5] 39
[7, 0, 6, 1, 2, 0, 0, 7, 0] 23 1.696

Ребро 0-4 платит 7 и исчерпывает вершину 0. Ребро 0-6 платить не может: у 0 остаток 0. Ребро 1-2 платит 6 - исчерпана вершина 2. Дальше 1-4 платит 1 (у 4 осталось 1), 1-5 - 2 (вершина 1 исчерпана), 3-5 - 7 (вершина 5 исчерпана). Оплачены 0, 1, 2, 4, 5: цена 39.

Сумма плат 23 - это нижняя граница, и она честная: оптимум 28 больше 23. Отношение 39 / 23 = 1,696 - это не догадка, а доказанная справка о конкретном ответе: «не хуже оптимума в 1,7 раза». Обычно такая справка лучше общей гарантии 2, потому что граница считается по этому же входу.

Разбор: порядок рёбер и чистка

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

def pryamo_dvojstvenno(ves, rebra):
    ostatok = ves[:]
    plata = 0
    for r in rebra:
        y = min(ostatok[r[0]], ostatok[r[1]])
        ostatok[r[0]] = ostatok[r[0]] - y
        ostatok[r[1]] = ostatok[r[1]] - y
        plata = plata + y
    pokrytie = []
    for v in range(len(ves)):
        if ostatok[v] == 0:
            pokrytie.append(v)
    return [pokrytie, plata]

def pokryvaet(rebra, nabor):
    for r in rebra:
        if r[0] not in nabor and r[1] not in nabor:
            return False
    return True

def pochistit(ves, rebra, pokrytie):
    # Лишние вершины выбрасываются, начиная с самых тяжёлых.
    ostavit = pokrytie[:]
    po_vesu = []
    for v in pokrytie:
        po_vesu.append([ves[v], v])
    po_vesu.sort(reverse=True)
    for para in po_vesu:
        bez = []
        for u in ostavit:
            if u != para[1]:
                bez.append(u)
        if pokryvaet(rebra, bez):
            ostavit = bez
    return sorted(ostavit)

def cena(ves, nabor):
    s = 0
    for v in nabor:
        s = s + ves[v]
    return s

ves = [7, 9, 6, 9, 8, 9, 5]
rebra = [[0, 4], [0, 6], [1, 2], [1, 4], [1, 5], [2, 4], [2, 6],
         [3, 5], [5, 6]]
for poryadok in [rebra, rebra[::-1]]:
    pp = pryamo_dvojstvenno(ves, poryadok)
    chisto = pochistit(ves, rebra, pp[0])
    print(pp[0], cena(ves, pp[0]), pp[1], chisto, cena(ves, chisto))

[0, 1, 2, 4, 5] 39 23 [0, 2, 4, 5] 30
[2, 4, 5, 6] 28 17 [2, 4, 5, 6] 28

Прямой порядок: 39, после чистки 30 - вершина 1 оказалась лишней (её рёбра закрыты вершинами 2, 4 и 5). Обратный: сразу 28 - оптимум - при сумме плат 17. Граница слабее, а ответ лучше: граница и ответ зависят от порядка независимо.

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

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

Принимают сумму плат за оптимум. 23 - граница снизу, оптимум 28. В отчёте пишут оба числа: ответ и границу.

Позволяют ребру платить больше остатка. Тогда у вершины плата превысит вес, двойственное решение станет недопустимым, и граница соврёт - может оказаться выше настоящего оптимума.

Не чистят ответ. В прямом порядке это 39 вместо 30 - на треть дороже на ровном месте.

Переносят метод на задачи без структуры «каждый элемент - не больше чем в f наборах». Для покрытия множествами тот же метод даёт гарантию f; если f велико, гарантия бесполезна, и нужен жадный алгоритм или случайное округление.

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

Прямо-двойственные алгоритмы - рабочая лошадь там, где граф огромный: один проход, никакой линейной программы, и к ответу прилагается граница. Та же схема - поднимать двойственные переменные, пока какое-то ограничение не станет тесным, и брать тесное в ответ - даёт приближённые алгоритмы для размещения предприятий, деревьев Штейнера, сетей с требованиями связности. Её же идея живёт внутри венгерского алгоритма о назначениях из раздела о потоках, где она даёт не приближение, а точный ответ.

Теперь сам

1. Звезда: центр весом 1, четыре луча весом 5. Что заплатят рёбра и что войдёт в покрытие?
2. Треугольник с весами 2, 3, 4, рёбра 0-1, 1-2, 0-2 по порядку. Проведи метод: платы, покрытие, сумма плат.
3. Почему сумма плат не больше оптимума, а не просто «примерно равна»?