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

== Решение ==

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