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

''Доказательство''. Когда жадный алгоритм выбирает множество s, предположим, что он назначает цену за элемент на этой итерации каждому элементу, впервые покрытому множеством s. Тогда совокупный вес множеств, выбранных алгоритмом, равен общей сумме назначенных цен, при этом каждому элементу цена назначается только один раз.

Рассмотрим любое множество <math>s = \{ x_k, x_{k - 1}, ... , x_1 \} \;</math> в оптимальном покрытии множества C*. Без потери общности предположим, что жадный алгоритм покрывает элементы s в следующем порядке: <math>x_k, x_{k - 1}, ..., x_1 \;</math>. К началу итерации, на которой алгоритм покрывает элемент <math>x_i \;</math> множества s, не менее i элементов s остаются без покрытия. Таким образом, если на этой итерации жадный алгоритм собирается выбрать s, он выплатит стоимость за каждый элемент не превышающую <math>w_s/i \;</math>. Следовательно, на этой итерации жадный алгоритм выплачивает не более <math>w_s/i \;</math> за каждый покрытый элемент. Таким образом, за покрытие элемента <math>x_i \;</math> он назначает не более <math>w_s/i \;</math>. Выполнив суммирование по i, получим, что общая сумма, назначенная за элементы s, не превышает <math>w_s H_k \;</math>. Выполнив суммирование по <math>s \in C^* \;</math> и заметив, что каждый элемент принадлежит к некоторому множеству в C*, получим, что общая сумма, назначенная за все элементы, не превышает <math>\sum_{s \in C^*} w_s H_k = H_k OPT \;</math>.  □

Эту теорему для невзвешенного случая (<math>w_s = 1 \;</math> для всех s) вначале доказали Джонсон [6], Ловас [9] и Стейн [14], после чего Хватал [2] расширил ее для взвешенного случая.