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

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

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

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

Пусть дано семейство 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 объектов, каждый объект 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.	Повторять, пока не будет достигнуто [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.	Вернуть C

Обозначим за [math]\displaystyle{ H_k \; }[/math] значение [math]\displaystyle{ \sum_{i = 1}^k 1 / i \approx ln \; k }[/math], где k – размер наибольшего множества.

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

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

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

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

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

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

Доказательство. Без потери общности предположим, что алгоритм покрывает элементы в порядке [math]\displaystyle{ x_n, x_{n - 1}, ..., x_1 \; }[/math]. К началу итерации, на которой алгоритм покрывает элемент [math]\displaystyle{ x_i \; }[/math], не менее i элементов остаются без покрытия, при этом все они могут быть покрыты при помощи нескольких множеств общей стоимостью OPT. Следовательно, существует некоторое множество, покрывающее еще не покрытые элементы, со стоимостью не более OPT/i на элемент.

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

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

Другие результаты

Было показано, что коэффициент аппроксимации жадного алгоритма составляет ln n - ln ln n + O(1) [12]. Для специального случая систем множеств, дополнения которых имеют конечную размерность Вапника - Червоненкиса (VC-размерность), другие алгоритмы демонстрируют заметно лучший коэффициент аппроксимации [1]. Известны аппроксимационные алгоритмы с постоянным коэффициентом для геометрических вариантов таких родственных задач, как метод k-медиан и задача о размещении объектов.

Жадный алгоритм можно естественным образом обобщить на множество задач. Например, для определенной выше задачи минимизации линейной функции относительно субмодулярных ограничений естественное расширение жадного алгоритма дает решение с [math]\displaystyle{ H_k \; }[/math]-аппроксимацией, где [math]\displaystyle{ k = max_{s \in S} f( \{s \}) - f(\empty) \; }[/math], в предположении, что f является целочисленной функцией [10].

Обобщая задачу о покрытии множества, можно потребовать, чтобы каждый элемент x содержался в произвольном числе множеств [math]\displaystyle{ r_x \; }[/math]; только в этом случае он будет считаться элементом покрытия. Для этого обобщения существует алгоритм O(log n)-аппроксимации с полиномиальным временем выполнения [8].

Для специального случая, когда каждый элемент принадлежит не более чем к r множествам, имеется более простой алгоритм r-аппроксимации ([15] § 15.2). Если множества имеют однородные веса ([math]\displaystyle{ w_s = 1 \; }[/math]), алгоритм сводится к следующему: выбрать любой максимальный набор элементов, никакие два из которых не содержатся в одном множестве; вернуть все множества, содержащие выбранный элемент.

В варианте «Максимальное k-покрытие» требуется, чтобы набор множеств, суммарный вес которых не превышает k, покрывал максимально возможное количество элементов. Для этого варианта существует алгоритм (1 - 1/e)-аппроксимации ([15], задача 2.18) (см. [7] для варианта множеств с неоднородными весами).

Широкое обсуждение применения жадных методов для аппроксимации задачи комбинаторной оптимизации можно найти в главе 4 работы [5].

Наконец, в свете весьма правдоподобных теоретико-сложностных допущений, коэффициент аппроксимации ln n является практически лучшим возможным для любого алгоритма с полиномиальным временем выполнения [3, 4].

Применение

Задача о покрытии множествами и ее обобщения и варианты являются фундаментальными для самых разных областей применения. Несколько примеров:

• выбор небольшого количества узлов сети для хранения файла таким образом, чтобы у всех узлов сети поблизости имелась его копия;

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

• выбор небольшого количества кадров для съемки с телескопом, на которых был бы отражен свет всех галактик в ночном небе;

• поиск короткой строки, содержащей каждую строку заданного множества в качестве последовательной подстроки.

См. также

• Локальный поиск для задачи о k-медианах и задачи о размещении объектов

Литература

1. Bronnimann, H., Goodrich, M.T.: Almost optimal set covers infinite VC-dimension. Discret. Comput. Geom. 14(4), 463-479 (1995)

2. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233-235 (1979)

3. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41 (5), 960-981 (1994)

4. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634-652 (1998)

5. Gonzalez, T.F.: Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC Computer & Information Science Series (2007)

6. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9,256-278 (1974)

7. Khuller, S., Moss, A., Naor, J.:The budgeted maximum coverage problem. Inform. Process. Lett. 70(1), 39^5 (1999)

8. Kolliopoulos, S.G., Young, N.E.: Tight approximation results for general covering integer programs. In: Proceedings of the forty-second annual IEEE Symposium on Foundations of Computer Science, pp. 522-528 (2001)

9. Lovasz, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13, 383-390 (1975)

10. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)

11. van Santen, J.P.H., Buchsbaum, A.L.: Methods for optimal text selection. In: Proceedings of the European Conference on Speech Communication and Technology (Rhodos, Greece) 2, 553-556(1997)

12. Slavik, P.: A tight analysis of the greedy algorithm for set cover. J. Algorithms 25(2), 237-254 (1997)

13. Srinivasan, A.: Improved approximations of packing and covering problems. In: Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing, pp. 268-276 (1995)

14. Stein, S.K.: Two combinatorial covering theorems. J. Comb. Theor. A 16, 391-397 (1974)

15. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin Heidelberg (2001)