Алгоритм присваивает «цену» 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).