Обсуждение:Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set — различия между версиями

Текущая версия на 17:00, 14 июня 2011

Решение

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