Жадные алгоритмы покрытия множества: различия между версиями

Теорема 2. Пусть S – система множеств над совокупностью с n элементами и весами ws < 1. Общий вес покрытия C, возвращаемого жадным алгоритмом, не превышает [1 + ln(n/OPT)]OPT + 1 (сравните со значением в [13]).

Доказательство. Без потери общности предположим, что алгоритм покрывает элементы в порядке xn, xn – 1, ; x1. К началу итерации, на которой алгоритм покрывает элемент xi, не менее i элементов остаются без покрытия, при этом все они могут быть покрыты при помощи нескольких множеств общей стоимостью OPT. Следовательно, существует некоторое множество, покрывающее еще не покрытые элементы, со стоимостью не более OPT/i на элемент.