Приблизительное покрытие

Алгоритм присваивает «цену» price(e) каждому элементу вселенной U, где эта цена представляет собой стоимость набора S, используемого для покрытия e, деленную на количество элементов, вновь покрываемых набором S (любые уже покрытые элементы должны быть назначена более низкая цена предыдущим набором из-за определения алгоритма).

Существует оптимальное решение, которое выбирает набор наборов общей стоимостью OPT. Поскольку это решение охватывает все элементы, оно, безусловно, охватывает и те элементы, которые еще не были охвачены. Покрытие остальных элементов (набор CBar в обозначении доказательства) по стоимости OPT означало бы покрытие каждого элемента с экономической эффективностью OPT/|CBar| по определению экономической эффективности (также известной как цена). Поскольку оптимальное решение содержит множество, покрывающее все остальные элементы, предположим, что мы выбираем множество S из оптимального решения, которое покрывает хотя бы один оставшийся элемент (e_k в лемме 2.3). Обратите внимание, что мы выбираем набор с наилучшей рентабельностью, поэтому его рентабельность должна быть не ниже средней рентабельности наборов в оптимальном решении OPT/|CBar|.

Последняя часть заключается в том, что из-за определений |CBar|=n-(k-1)=n-k+1 как k-1 элементы уже покрыты, и мы рассматриваем покрывающий элемент k. Таким образом, рентабельность S и, следовательно, price(e_k) ограничена OPT/(n-k+1).