Мультиразрез: отделить все терминалы друг от друга

Если отличаешь multiway cut от произвольных пар multicut - переходи к «Теперь сам».

Как думаешь: достаточно ли самого дешёвого парного разреза?

Три сервиса должны оказаться в разных изолированных сетевых зонах. Разрез между первым и вторым может оставить третий вместе с первым. Следующий парный разрез снова делит граф, но его рёбра могут перекрываться с уже выбранными. Независимая сумма цен не равна цене объединения, а локальная дешевизна не обеспечивает глобальный оптимум.

В этой постановке отделяются все пары терминалов. Другая задача, multicut, задаёт отдельный список запрещённых пар. Её название иногда тоже переводят словом «мультиразрез», поэтому перед применением алгоритма нужно уточнить именно множество требований, а не доверять переводу названия.

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

Представь три закрытых двора, соединённые проходами разной стоимости. Нужно перекрыть проходы так, чтобы из одного двора нельзя было дойти в другой. У каждого двора можно поставить своё минимальное кольцо ограждений. Если ограждены два двора, третий уже отделён от обоих: отдельное кольцо вокруг него не требуется. Общие ограждения считаются один раз, что может сделать объединение дешевле суммы.

Механизм: изолирующие разрезы и двойной счёт

Для каждого терминала s_i найдём минимальный разрез, отделяющий его от всех остальных терминалов одновременно. Для этого остальные можно стянуть в одну стоковую вершину и решить обычную задачу минимального разреза. Обозначим набор удаляемых рёбер F_i. Возьмём k − 1 самых дешёвых таких наборов и объединим. Любая пара терминалов содержит хотя бы один из выбранных; его изолирующий разрез запрещает путь ко второму. Поэтому ответ допустим.

Рассмотрим оптимальный мультиразрез. Компонента каждого терминала имеет границу, которая сама является допустимым изолирующим разрезом. Наш минимальный F_i стоит не больше этой границы. В сумме границ каждое ребро оптимального решения учитывается не больше двух раз: оно имеет два конца. Значит, сумма цен всех найденных изолирующих разрезов не больше 2·OPT. Удаление самого дорогого уменьшает эту сумму хотя бы на её 1/k долю. Цена объединения не больше суммы цен оставшихся наборов, что и даёт 2(1 − 1/k)·OPT.

Можно получить другую релаксацию через координаты. Терминалу i назначается вектор e_i: единица на позиции i, нули на остальных. Обычной вершине v - неотрицательные координаты x_v, сумма которых равна единице. Такое множество векторов называется симплексом. Целочисленное разбиение выбирает только вершины симплекса; релаксация разрешает промежуточные точки.

Цена ребра в релаксации: w_uv · ||x_u − x_v||₁/2, где норма ||z||₁ - сумма абсолютных значений координат. У одинаковых целых меток расстояние ноль, у разных равно двум, поэтому формула совпадает с весом разрезанного ребра. Для округления выбирают общий случайный радиус r ∈ (0,1) и случайный порядок терминалов. Первые k − 1 терминалов забирают ещё не назначенные вершины в свой шар ||e_i − x_v||₁/2 ≤ r; оставшиеся вершины получает последний. Терминалы не попадают в чужие шары при r < 1. Полученное разбиение допустимо; оценка качества такого ЛП-округления требует отдельного анализа. Граница из предыдущего абзаца доказана для изолирующих разрезов, а не перенесена на эту процедуру по сходству.

Правило

Для multiway cut объединение всех, кроме самого дорогого, минимальных изолирующих разрезов даёт (2 − 2/k)-приближение. Общие рёбра в ответе считаются один раз. Речь о неориентированных графах, неотрицательных весах и всех парах различных терминалов.

Разбор: три терминала и одна общая вершина

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

from itertools import product


rebra = [(0, 3, 2), (1, 3, 2), (2, 3, 2)]
terminaly = [0, 1, 2]


def granica(s):
    return {i for i, (u, v, _) in enumerate(rebra)
            if (u in s) != (v in s)}


def cena(f):
    return sum(rebra[i][2] for i in f)


def izolirovat(t):
    kandidaty = []
    for bits in product([False, True], repeat=4):
        s = {v for v, b in enumerate(bits) if b}
        if t in s and all(u not in s for u in terminaly if u != t):
            f = granica(s)
            kandidaty.append((cena(f), sorted(f)))
    _, f = min(kandidaty)
    return set(f)


razrezy = sorted((izolirovat(t) for t in terminaly),
                 key=lambda f: (cena(f), sorted(f)))
otvet = set().union(*razrezy[:-1])
opt = min(sum(w for u, v, w in rebra if metki[u] != metki[v])
          for metki in [(0, 1, 2, c) for c in terminaly])
print('цены изолирующих:', [cena(f) for f in razrezy])
print('алгоритм:', cena(otvet))
print('оптимум:', opt)
print('оценка для k=3:', round((2 - 2 / 3) * opt, 6))

цены изолирующих: [2, 2, 2]
алгоритм: 4
оптимум: 4
оценка для k=3: 5.333333

Алгоритм на этом графе оптимален, но теорема обещает лишь верхнюю границу 16/3. Гарантия - предел на худшем входе, не предсказание точного результата любого запуска. Перебор меток центра перечисляет все допустимые разбиения: терминальные метки зафиксированы.

Разбор: центр симплекса не является готовой меткой

В той же звезде можно поставить центр в (1/3,1/3,1/3). Его расстояние ||e_i − x||₁/2 до каждого терминала равно 2/3. Цена каждого ребра в релаксации 4/3, общая цена четыре. Если радиус меньше 2/3, центр остаётся последнему терминалу. Если больше, его заберёт первый. В обоих случаях после округления удаляются два ребра веса два. Дробные координаты описывают возможность нескольких назначений; их нельзя интерпретировать как «треть сервиса живёт в каждой зоне» в исходной дискретной задаче.

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

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

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

Размещение связанных объектов на заранее закреплённых машинах и изоляция сетевых зон требуют учёта стоимости связи через границу. Терминалы фиксируют обязательные назначения, обычные вершины выбирают размещение. Модель не требует одинакового размера групп; если добавить ограничения вместимости или баланс, приведённая гарантия уже не относится к новой задаче автоматически.

Теперь сам

Четыре терминала. Минимальные изолирующие разрезы стоят 3,4,5,8. Какую верхнюю оценку цены объединения даёт алгоритм до учёта общих рёбер? Какова общая гарантия относительно OPT?