Округление по порогу: взвешенное вершинное покрытие

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

Как думаешь, что пойдёт не так с весами

В главе о жадных алгоритмах вершинное покрытие решалось приёмом «пока есть непокрытое ребро, взять оба его конца»: гарантия 2. Там же было сказано, что для покрытия с весами этот приём не годится. Посмотри почему. Перекрёсток в центре, четыре улицы-луча; камера в центре стоит 1, на концах лучей - по 5.

Ответь себе до чтения: что возьмёт приём «оба конца»? Первое же ребро - центр и конец луча, 1 + 5 = 6. Оптимум - одна камера в центре за 1. Шестикратная переплата, и, меняя 5 на 500, можно сделать любую. Приёму всё равно, сколько стоят вершины. Нужен способ, который на вес смотрит, - и его даёт линейная программа.

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

Голосование в долях. Каждое ребро требует, чтобы его концы вместе набрали хотя бы единицу «присутствия»; каждая единица присутствия вершины стоит её вес. Самое дешёвое распределение долей - это и есть релаксация. Потом объявляют правило: вершина входит в ответ, если набрала не меньше половины.

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

Механизм: релаксация, порог и цена

Целочисленная программа для взвешенного покрытия:

минимизировать   Σ w_v · x_v
при условиях     x_u + x_v >= 1      для каждого ребра u-v
                 x_v ∈ {0, 1}
релаксация:      0 <= x_v <= 1       вместо {0, 1}
                 её оптимум LP <= OPT

Округление по порогу. Взять v, если x_v ≥ 1/2.

покрытие:  x_u + x_v >= 1  ⇒  max(x_u, x_v) >= 1/2
           ⇒  хотя бы один конец взят
цена:      взятая v платит w_v <= 2 · w_v · x_v   (ведь x_v >= 1/2)
           Σ взятых <= 2 · Σ w_v · x_v = 2 · LP <= 2 · OPT

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

Как решить релаксацию. Немхаузер и Троттер (1975) доказали, что у ЛП вершинного покрытия все вершины многогранника состоят из чисел 0, 1/2 и 1. Значит, оптимум можно искать среди таких наборов: для небольшого графа - перебором 3ⁿ вариантов, для большого - симплекс-методом или, что ещё быстрее, сведением к потоку.

Разрыв целочисленности - точная верхняя грань (к ней можно подойти сколь угодно близко) отношения целого оптимума к оптимуму релаксации. Доказательство «ответ ≤ c · LP ≤ c · OPT» не может дать c меньше этого разрыва: на входе с разрывом g даже идеальный ответ равен g · LP.

Правило

Округление по порогу: решить ЛП-релаксацию взвешенного вершинного покрытия и взять вершины с x_v ≥ 1/2. Это покрытие, и его цена не больше 2 · LP ≤ 2 · OPT. Разрыв целочисленности этой релаксации стремится к двум, поэтому анализ через неё лучше двойки не даст.

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

luchshee перебирает наборы значений: с тремя значениями (0, 1, 2 - это 0, 1/2 и 1 в половинках) - это релаксация, с двумя - целый оптимум. Ограничение «ребро покрыто» в половинках - x_u + x_v ≥ 2. Для сравнения - приём oba_konca.

def pokryto(rebra, x, porog):
    for r in rebra:
        if x[r[0]] + x[r[1]] < porog:
            return False
    return True

def luchshee(ves, rebra, znachenij):
    n = len(ves)
    best = [-1, []]
    for kod in range(znachenij ** n):
        x = []
        k = kod
        for v in range(n):
            x.append(k % znachenij)
            k = k // znachenij
        if pokryto(rebra, x, znachenij - 1):
            cena = 0
            for v in range(n):
                cena = cena + ves[v] * x[v]
            if best[0] == -1 or cena < best[0]:
                best = [cena, x]
    return best

def oba_konca(n, rebra):
    vzyato = [0] * n
    for r in rebra:
        if vzyato[r[0]] == 0 and vzyato[r[1]] == 0:
            vzyato[r[0]] = 1
            vzyato[r[1]] = 1
    return vzyato

def cena(ves, x):
    s = 0
    for v in range(len(ves)):
        s = s + ves[v] * x[v]
    return s

grafy = [[[1, 5, 5, 5, 5], [[1, 0], [2, 0], [3, 0], [4, 0]]],
         [[7, 9, 6, 9, 8, 9, 5],
          [[0, 4], [0, 6], [1, 2], [1, 4], [1, 5], [2, 4], [2, 6],
           [3, 5], [5, 6]]]]
for g in grafy:
    ves = g[0]
    rebra = g[1]
    lp = luchshee(ves, rebra, 3)
    vzyat = []
    for v in range(len(ves)):
        if lp[1][v] >= 1:
            vzyat.append(1)
        else:
            vzyat.append(0)
    tochno = luchshee(ves, rebra, 2)
    print(lp[0] / 2, lp[1])
    oba = oba_konca(len(ves), rebra)
    print(cena(ves, vzyat), tochno[0], cena(ves, oba))

1.0 [2, 0, 0, 0, 0]
1 1 6
26.5 [1, 1, 1, 1, 1, 1, 1]
53 28 48

Звезда: релаксация ставит центру единицу (2 в половинках), лучам ноль - она сразу целая. Округление берёт центр, цена 1 - оптимум. Приём «оба конца» - 6.

Граф из семи вершин: релаксация - всем по половине, 26,5. Округление берёт все вершины: 53. Это ровно 2 · 26,5 - гарантия выполнена впритык. Целый оптимум 28, так что ответ хуже оптимума в 1,89 раза. «Оба конца» здесь дали 48 - лучше, но это везение: на звезде тот же приём переплатил вшестеро, а гарантии с весами у него нет.

Деталь, которая стоит запоминания: у этой релаксации есть и другая оптимальная точка с той же ценой 26,5 - с нулём у вершины 3 и единицей у вершины 5. Её округление стоило бы 44. Метод гарантирует «не больше двух LP» для любой оптимальной точки, но качество на конкретном входе зависит от того, какую точку вернул решатель.

Разбор: полный граф и предел метода

Полный граф на n вершинах, все веса 1: каждая пара соединена. Целый оптимум - n − 1 вершина (если две вершины не взяты, ребро между ними не покрыто). Релаксация - всем по половине.

def pokryto(rebra, x, porog):
    for r in rebra:
        if x[r[0]] + x[r[1]] < porog:
            return False
    return True

def luchshee(n, rebra, znachenij):
    best = -1
    for kod in range(znachenij ** n):
        x = []
        k = kod
        for v in range(n):
            x.append(k % znachenij)
            k = k // znachenij
        if pokryto(rebra, x, znachenij - 1):
            if best == -1 or sum(x) < best:
                best = sum(x)
    return best

for n in [3, 4, 5, 6, 7]:
    rebra = []
    for a in range(n):
        for b in range(a + 1, n):
            rebra.append([a, b])
    lp = luchshee(n, rebra, 3) / 2
    celoe = luchshee(n, rebra, 2)
    print(n, lp, celoe, round(celoe / lp, 3))

3 1.5 2 1.333
4 2.0 3 1.5
5 2.5 4 1.6
6 3.0 5 1.667
7 3.5 6 1.714

Отношение целого к релаксации - (n − 1) / (n / 2) = 2 − 2/n, оно растёт к двум. На полном графе из ста вершин релаксация 50, а покрытия дешевле 99 нет. Значит, никакое округление этой релаксации не докажет гарантию лучше 2 − 2/n: граница LP слишком низко. Это не значит, что двойку побить нельзя в принципе, - нужна другая граница. Есть ли она, вопрос главы о пределах приближенияРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: PCP и карта границ: где простые алгоритмы оказались лучшими возможными.

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

Берут «оба конца» для весов. На звезде с дешёвым центром - переплата во сколько угодно раз.

Округляют до ближайшего целого. При x_v = 1/2 «до ближайшего» неоднозначно, и если оба конца ребра по половине округлить вниз, ребро останется непокрытым. Порог - именно ≥ 1/2.

Переносят порог 1/2 на покрытие множествами. Там элемент может входить в f множеств, и доли могут быть по 1/f у каждого. Порог 1/2 их все отбросит. Нужен порог 1/f - следующий урокРазбирается в разделе 22, глава «ЛП-округление и прямо-двойственный метод»: Округление покрытия множеств: порог 1/f и случайный выбор.

Сравнивают с целым оптимумом, а доказывают через LP. Гарантия - «не больше двух LP»; отношение к целому оптимуму бывает лучше, но доказана только эта граница.

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

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

Теперь сам

1. Треугольник, все веса 1. Какова релаксация, что даст округление по порогу и каков оптимум?
2. Ребро u-v, веса w_u = 1, w_v = 10. Какова оптимальная точка релаксации и что возьмёт округление?
3. Почему из x_u + x_v ≥ 1 следует, что хотя бы один конец набрал не меньше половины?