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

Пусть дано семейство S множеств над совокупностью U. ''Покрытие множества'' <math>C \subseteq S \;</math> представляет собой подсемейство множеств, объединением которых является U. ''Задача о покрытии множества'' заключается в нахождении покрытия множествами с минимальной мощностью для заданного S. В ''задаче о взвешенном покрытии множества'' для каждого множества <math>s \in S \;</math> задается вес <math>w_s \ge 0 \;</math>, и цель заключается в нахождении покрытия множества C с минимальным совокупным весом <math>\sum_{s \in C} w_s \;</math>.

Взвешенное покрытие множества представляет собой специальный случай ''минимизации линейной функции относительно субмодулярных ограничений'', определяемый следующим образом. Пусть дано семейство S объектов, каждый из которых имеет неотрицательный вес <math>w_s \;</math>, и неубывающая субмодулярная функция <math>f: 2^S \to \mathbb{R}</math>. Задача заключается в нахождении подсемейства <math>C \subseteq S \;</math>, такого, что <math>f(C) = f(S) \;</math> минимизирует <math>\sum_{s \in C} w_s \;</math>. (Если положить <math>f(C) = |\cup_{s \in C} s|</math>, получим задачу о взвешенном покрытии множества).