Округление покрытия множеств: порог 1/f и случайный выбор

Если ты знаешь, почему порог для покрытия множествами - 1/f, как случайное округление накрывает все элементы за порядка ln n раундов и почему гарантия не выбирает алгоритм за тебя, листай до «Теперь сам».

Как думаешь, какой порог нужен

Двенадцать элементов, десять множеств с ценами; каждый элемент входит в два или три множества. Релаксация вернула доли: несколько множеств по 2/3, несколько по 1/3, одно целиком. Попробуй порог 1/2 из прошлого урока.

Ответь себе до чтения: всё ли накроется? Элемент, который лежит в трёх множествах по 1/3, набрал ровно единицу, но ни одно его множество не дотянуло до половины - элемент останется непокрытым. Порог 1/2 годился для рёбер, у которых два конца. У элемента три «конца», и порог должен быть 1/3.

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

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

Случайное округление - другая игра: каждый вкладчик подбрасывает монетку со своей вероятностью. Касса, в которую внесли единицу, остаётся пустой с вероятностью не больше 1/e ≈ 0,37 за раунд - и после нескольких раундов почти наверняка не пустая.

Механизм: два способа округлить

Релаксация покрытия множествами:

минимизировать   Σ c_j · x_j
при условиях     Σ x_j >= 1  по множествам j, содержащим элемент e
                 0 <= x_j <= 1
f = наибольшее число множеств, содержащих один элемент

Порог 1/f. Взять множество j, если x_j ≥ 1/f. У элемента не больше f множеств, сумма их долей не меньше единицы - значит, хотя бы одна доля не меньше 1/f: элемент накрыт. Цена: взятое множество платит c_j ≤ f · c_j · x_j, итого не больше f · LP ≤ f · OPT.

Случайное округление. Раунд: каждое множество берётся независимо с вероятностью x_j. Элемент e остаётся непокрытым, если не взято ни одно его множество:

P(e не накрыт за раунд) = Π (1 − x_j) <= Π e^(−x_j)
                        = e^(−Σ x_j) <= e^(−1)

Здесь использовано 1 − x ≤ e^(−x) - то же неравенство, что в разделе о случайности для разреза Каргера. За t раундов элемент не накрыт с вероятностью не больше e^(−t). При t = 2 ln n это 1/n², а то, что непокрыт хоть один из n элементов, - не больше n · 1/n² = 1/n. Каждый раунд стоит в ожидании ровно LP, значит, 2 ln n раундов - не больше 2 ln n · LP; если после них что-то не накрыто (вероятность не больше 1/n), его докрывают, и ожидаемая цена остаётся O(ln n) · LP. Логарифм вместо f - выгодно, когда множества сильно перекрываются.

Правило

Для покрытия множествами порог округления - 1/f, где f - наибольшая частота элемента: это покрытие ценой не больше f · LP. Случайное округление (каждое множество с вероятностью x_j, раунды до полного покрытия) за O(ln n) раундов накрывает всё с высокой вероятностью при ожидаемой цене O(ln n) · LP. Гарантии - про худший вход; на конкретном входе алгоритмы сравнивают замером.

Разбор: порог против жадности

Двенадцать элементов, десять множеств. Релаксацию решает linprog - он понимает только ограничения «не больше», поэтому «каждый элемент накрыт хотя бы раз» передано как −A·x ≤ −1; целый оптимум - milp; жадность - из главы о жадных алгоритмах: множество с наименьшей ценой на новый элемент. Программа запускается в обычном Python со scipy.

import numpy as np
from scipy.optimize import linprog, milp, LinearConstraint, Bounds

mnozhestva = [[3, 4], [2, 5, 8], [0, 1, 4, 6], [0, 1, 7, 11],
              [0, 3, 4, 5, 6, 9, 11], [8], [6, 7, 8], [7, 9, 10],
              [2], [9, 10]]
cena = [3, 9, 6, 5, 6, 8, 5, 5, 7, 3]
n = 12
m = len(mnozhestva)
A = np.zeros((n, m))
for j in range(m):
    for e in mnozhestva[j]:
        A[e, j] = 1
f = int(A.sum(axis=1).max())

lp = linprog(cena, A_ub=-A, b_ub=-np.ones(n), bounds=(0, 1))
celoe = milp(cena, integrality=np.ones(m), bounds=Bounds(0, 1),
             constraints=[LinearConstraint(A, 1, np.inf)])
vzyaty = [j for j in range(m) if lp.x[j] >= 1 / f - 0.000001]

def zhadno():
    nenakryto = set(range(n))
    vybor = []
    while nenakryto:
        def udelnaya(j):
            novyh = len(nenakryto & set(mnozhestva[j]))
            return cena[j] / novyh if novyh else float("inf")
        j = min(range(m), key=udelnaya)
        vybor.append(j)
        nenakryto -= set(mnozhestva[j])
    return vybor

print(f, round(lp.fun, 2), round(celoe.fun, 2))
print([round(abs(float(v)), 2) for v in lp.x])
print(vzyaty, sum(cena[j] for j in vzyaty))
print(zhadno(), sum(cena[j] for j in zhadno()))

3 22.33 23.0
[0.67, 0.67, 0.33, 0.67, 0.33, 0.0, 0.33, 0.0, 0.33, 1.0]
[0, 1, 2, 3, 4, 6, 8, 9] 44
[4, 3, 9, 1] 23

f = 3. Релаксация 22,33, целый оптимум 23: релаксация здесь почти точна. Но её доли - сплошь трети и две трети. Порог 1/3 берёт восемь множеств из десяти, цена 44: вдвое хуже оптимума, хотя в пределах гарантии 3 · 22,33 = 67.

Жадность взяла множество 4 (семь элементов за 6 - по 0,86 на элемент), потом 3, 9 и 1 - и попала ровно в оптимум 23. Её гарантия H(12) ≈ 3,1 хуже тройки, а ответ на этом входе вдвое лучше. Это та же история, что в главе о жадных алгоритмах: гарантия ограничивает худший вход, а не обещает лучший ответ на твоём.

Разбор: случайное округление на тех же данных

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

import math
import random
import numpy as np
from scipy.optimize import linprog

mnozhestva = [[3, 4], [2, 5, 8], [0, 1, 4, 6], [0, 1, 7, 11],
              [0, 3, 4, 5, 6, 9, 11], [8], [6, 7, 8], [7, 9, 10],
              [2], [9, 10]]
cena = [3, 9, 6, 5, 6, 8, 5, 5, 7, 3]
n = 12
m = len(mnozhestva)
A = np.zeros((n, m))
for j in range(m):
    for e in mnozhestva[j]:
        A[e, j] = 1
x = linprog(cena, A_ub=-A, b_ub=-np.ones(n), bounds=(0, 1)).x

def sluchajno(zerno):
    random.seed(zerno)
    vzyato = set()
    raundov = 0
    while any(all(j not in vzyato for j in range(m) if A[e, j])
              for e in range(n)):
        raundov += 1
        for j in range(m):
            if random.random() < x[j]:
                vzyato.add(j)
    return raundov, sum(cena[j] for j in vzyato)

itogi = [sluchajno(z) for z in range(1, 11)]
print([r for r, c in itogi])
print([c for r, c in itogi])
print(round(math.log(n), 2))

[2, 2, 1, 1, 2, 3, 1, 2, 2, 3]
[32, 26, 32, 26, 32, 29, 32, 32, 37, 33]
2.48

Раундов от одного до трёх - меньше, чем ln 12 ≈ 2,48 в среднем, как и обещает оценка: каждый элемент за раунд остаётся пустым с вероятностью не больше 0,37. Цена от 26 до 37: лучше порога 44, хуже жадности 23.

Почему не лучше: каждый раунд в ожидании стоит 22,33, а два раунда - уже 44,7, и спасает только то, что повторно взятое множество не оплачивается дважды. На двенадцати элементах ln n - не выигрыш перед f = 3. Случайное округление окупается, когда элементов тысячи, а частоты - десятки: тогда ln n ≈ 7 против f = 50.

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

Порог 1/2 для множеств. Элемент с тремя долями по трети остаётся непокрытым. Порог зависит от f.

Один раунд случайного выбора. Элемент пуст с вероятностью до 37%; из тысячи элементов непокрытыми в ожидании останутся сотни. Раунды повторяют, а после них проверяют и, если нужно, докрывают жадно.

Выбор по гарантии. Порог гарантирует 3, жадность - 3,1, а на входе они дали 44 и 23. Если входы известны, выбирают замером; гарантия нужна, чтобы знать худший случай.

Округляют не оптимум релаксации. Анализ опирается на то, что сумма долей - это LP; если взять неоптимальные доли, гарантия считается от их суммы, а не от LP.

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

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

Теперь сам

1. Элемент входит в пять множеств, все доли 0,2. Какой порог нужен и что он даст для этого элемента?
2. Почему вероятность, что элемент не накрыт за раунд случайного округления, не больше 1/e?
3. Элементов 10 000. Сколько раундов нужно, чтобы вероятность хоть одного непокрытого была не больше 1/n?