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

Ссылки сюда (10) →

Жадный алгоритм: на -ом шаге добавляем элемент , который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов .

Пусть на -ом шаге осталось подмножеств, в которых не содержаться ни один из элементов . Пусть также размер оптимального hitting seta равен , а изначально было подмножеств. Тогда на - ом шаге будет покрыто не менее объектов. Действительно, иначе оптимальный hitting set не покрывал бы и оставшиеся подмножества. В результате, А значит,

Требуя, чтобы правая часть неравенства была меньше единицы, то есть полное покрытие всего семейства получам, что

Но - и есть число элементов в жадном hitting set-е. Значит получена оценка на точность.

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

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

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