Комментарии — Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set

Решение

Задача аналогична задаче о поиске покрытия из курса. На каждом шаге добавляем в S такой элемент, котороый содержится в наибольшем количестве еще не покрытых множеств. Таким образом, будет так же справедлива оценка X_k+1 <= X_k(1-1/M) и мощность множества S, построенного данным алгоритмом, будет превосходить мощность S*, построенного оптимальным алгоритмом, не более чем в 1+ln(m) раз, где m - количество подмножеств в данном семействе.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.