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

Ключевые слова и синонимы

Доминирующее множество; жадный алгоритм; множество представителей; покрытие множества; минимизация линейной функции относительно субмодулярных ограничений

Постановка задачи

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

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

Основные результаты

Жадный алгоритм решения задачи о взвешенном покрытии множества строит покрытие путем многократного выбора множества s, минимизирующего отношение веса [math]\displaystyle{ w_s \; }[/math] к количеству элементов в s, еще не покрытого выбранными множествами. Алгоритм останавливает работу и возвращает выбранные множества, как только они образуют покрытие:

  greedy-set-cover(S, w)
  1.	Инициализировать [math]\displaystyle{ C \gets \empty \; }[/math]. Определить [math]\displaystyle{ f(C) \; \dot= \; |\cup_{s \in C} s| }[/math].
  2.	Repeat until [math]\displaystyle{ f(C) = f(S) \; }[/math]:
  3.	Выбрать [math]\displaystyle{ s \in S \; }[/math], минимизирующий стоимость на элемент [math]\displaystyle{ w_s / [f(C \cup \{ s \}) - f(C)] }[/math].
  4.	Положить [math]\displaystyle{ C \gets C \cup \{ s \} }[/math].
  5.	Return C

Обозначим за Hk значение Pki=1 1/i ^ m k, где k – размер наибольшего множества.

Теорема 1. Жадный алгоритм возвращает покрытие множества, вес которого не более чем в Hk раз превышает минимальный вес любого покрытия.

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

Рассмотрим любое множество s = fxk, x, ,x\) в оптимальном покрытии множества C*. Без потери общности предположим, что жадный алгоритм покрывает элементы s в следующем порядке: xk, xk - 1, x1. К началу итерации, на которой алгоритм покрывает элемент xi множества s, не менее i элементов s остаются без покрытия. Таким образом, если на этой итерации жадный алгоритм собирается выбрать s, он выплатит стоимость за каждый элемент не превышающую ws/i. Следовательно, на этой итерации жадный алгоритм выплачивает не более ws/i за каждый покрытый элемент. Таким образом, за покрытие элемента xi он назначает не более ws/i. Выполнив суммирование по i, получим, что общая сумма, назначенная за элементы s, не превышает ws Hk. Выполнив суммирование по s 2 C* и заметив, что каждый элемент принадлежит к некоторому множеству в C*, получим, что общая сумма, назначенная за все элементы, не превышает X!sec* wsHk = HkOPT. □

Эту теорему для невзвешенного случая (ws = 1 для всех s) вначале доказали Джонсон [ ], Ловас [ ] и Стейн [14], после чего Хватал [2] расширил ее для взвешенного случая.

С тех пор было предложено несколько уточнений и дополнений, включая следующее:

Теорема 2. Пусть S – система множеств над совокупностью с n элементами и весами ws < 1. Общий вес покрытия C, возвращаемого жадным алгоритмом, не превышает [1 + ln(n/OPT)]OPT + 1 (сравните со значением в [13]).

Доказательство. Без потери общности предположим, что алгоритм покрывает элементы в порядке xn, xn – 1, ; x1. К началу итерации, на которой алгоритм покрывает элемент xi, не менее i элементов остаются без покрытия, при этом все они могут быть покрыты при помощи нескольких множеств общей стоимостью OPT. Следовательно, существует некоторое множество, покрывающее еще не покрытые элементы, со стоимостью не более OPT/i на элемент.

Вспомним схему назначения стоимости из доказательства теоремы 1. Согласно предыдущему наблюдению, элементу xi назначается стоимость не более OPT/i. Таким образом, общая стоимость элементов xn... xi не превышает (Hn — H,_I)OPT. В силу предположения о том, что каждый вес ws < 1, стоимость каждого из оставшихся элементов не превышает 1 за элемент. Таким образом, совокупная стоимость всех элементов не превышает i — 1 + (Hn — H,_I)OPT. Приняв i = 1 + dOPTe, получаем, что совокупная стоимость не превышает dOPTe + (Hn - HdOPTe )OPT - 1 + OPT(1 + ln(n/OPT)). □

Каждое из вышеприведенных доказательств неявно строит прямо-двойственную пару задач линейного программирования для выявления коэффициента аппроксимации. Эти же коэффициенты аппроксимации можно получить относительно любого частного оптимума (решения частичной задачи о покрытии множества методом линейного программирования).