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

Вспомним схему назначения стоимости из доказательства теоремы 1. Согласно предыдущему наблюдению, элементу <math>x_i \;</math> назначается стоимость не более OPT/i. Таким образом, общая стоимость элементов <math>x_n, ..., x_i \;</math> не превышает <math>(H_n - H_{i - q})OPT \;</math>. В силу предположения о том, что каждый вес <math>w_s \le 1 \;</math>, стоимость каждого из оставшихся элементов не превышает 1 за элемент. Таким образом, совокупная стоимость всех элементов не превышает <math>i - 1 + (H_n - H_{i - 1})OPT \;</math>. Обозначив <math>i = 1 + \lceil OPT \rceil</math>, получаем, что совокупная стоимость не превышает dOPTe + (Hn - HdOPTe )OPT - 1 + OPT(1 + ln(n/OPT)). □