Введение
Классическая задача в комбинаторике
Задача о покрытии множества – классический вопрос в комбинаторике, информатике, исследовании операций и теории сложности. Дано множество элементов {1, 2, ..., n} (называемое универсальным множеством) и коллекция S из m подмножеств, объединение которых равно универсальному множеству, задача о покрытии множества состоит в том, чтобы найти наименьшее подмножество S, объединение которого равно универсальному множеству. Например, рассмотрим универсальное множество U = {1, 2, 3, 4, 5} и коллекцию множеств S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. Очевидно, что объединение S равно U. Однако мы можем покрыть все элементы всего двумя множествами: { {1, 2, 3}, {4, 5} }, как показано на рисунке. Следовательно, решение задачи о покрытии множества имеет размер 2. Более формально, задано универсальное множество и семейство подмножеств, покрытие множества – это подсемейство множеств, объединение которых равно универсальному множеству. В задаче принятия решения о покрытии множества на вход подается пара и целое число k; вопрос заключается в том, существует ли покрытие множества размера k или меньше. В задаче оптимизации покрытия множества на вход подается пара , и требуется найти покрытие множества, использующее минимальное количество множеств. Задача принятия решения о покрытии множества является NP-полной. Это одна из 21 NP-полных задач Карпа, показанных NP-полными в 1972 году. Задача оптимизации/поиска покрытия множества является NP-трудной. Это проблема, "изучение которой привело к разработке фундаментальных методов для всей области" алгоритмов аппроксимации.
In the set cover decision problem, the input is a pair and an integer ; the question is whether there is a set cover of size or less. In the set cover optimization problem, the input is a pair , and the task is to find a set cover that uses the fewest sets. The decision version of set covering is NP complete. It is one of Karp's 21 NP complete problems shown to be NP complete in 1972. The optimization/search version of set cover is NP hard. It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.
Варианты
В задаче о покрытии множеств с весами каждому множеству присваивается положительный вес (представляющий его стоимость), и цель состоит в нахождении покрытия множеств с минимальным весом. Обычное (не взвешенное) покрытие множеств соответствует случаю, когда все множества имеют вес 1. В задаче о дробном покрытии множеств разрешается выбирать части множеств, а не целые множества. Дробное покрытие множеств – это присвоение каждому множеству из некоторой доли (числа в [0,1]), такое что для каждого элемента x из универсального множества сумма долей множеств, содержащих x, не меньше 1. Цель состоит в нахождении дробного покрытия множеств, в котором сумма долей минимальна. Следует отметить, что (обычное) покрытие множеств эквивалентно дробному покрытию множеств, в котором все доли равны либо 0, либо 1; следовательно, размер минимального дробного покрытия не превосходит размера минимального покрытия, но может быть и меньше. Например, рассмотрим универсальное множество U = {1, 2, 3} и коллекцию множеств S = { {1, 2}, {2, 3}, {3, 1} }. Минимальное покрытие множеств имеет размер 2, например, { {1, 2}, {2, 3} }. Но существует дробное покрытие множеств размером 1.5, в котором берется доля 0.5 от каждого множества.
Формулирование линейной программы
Проблема покрытия множества может быть сформулирована как следующая целочисленная линейная программа (ILP). Минимизировать (минимизировать число множеств) при условиях: для всех (покрыть каждый элемент вселенной) для всех (каждое множество либо входит в покрытие, либо нет). Для более компактного представления ограничения покрытия можно определить матрицу инцидентности, где каждая строка соответствует элементу, а каждый столбец – множеству, и если элемент e принадлежит множеству s, и иначе. Тогда ограничение покрытия можно записать как:
Взвешенное покрытие множества описывается программой, идентичной приведенной выше, за исключением того, что целевая функция, которую нужно минимизировать, – это , где – вес множества .
Дробное покрытие множества описывается программой, идентичной приведенной выше, за исключением того, что переменные могут быть нецелочисленными, поэтому последнее ограничение заменяется на .
Эта линейная программа относится к более общему классу линейных программ для задач покрытия, поскольку все коэффициенты в целевой функции и обе части ограничений неотрицательны. Целочисленный разрыв ILP не превышает (где – размер вселенной). Показано, что ее релаксация действительно дает аппроксимационный алгоритм с коэффициентом для задачи минимального покрытия множества. Подробное объяснение см. в разделе "Случайное округление" (randomized rounding) #setcover.
For a more compact representation of the covering constraint, one can define an incidence matrix , where each row corresponds to an element and each column corresponds to a set, and if element e is in set s, and otherwise. Then, the covering constraint can be written as
Weighted set cover is described by a program identical to the one given above, except that the objective function to minimize is , where is the weight of set
Fractional set cover is described by a program identical to the one given above, except that can be non integer, so the last constraint is replaced by
This linear program belongs to the more general class of LPs for covering problems, as all the coefficients in the objective function and both sides of the constraints are non negative. The integrality gap of the ILP is at most (where is the size of the universe). It has been shown that its relaxation indeed gives a factor approximation algorithm for the minimum set cover problem. See randomized rounding#setcover for a detailed explanation.
Низкочастотные системы
Если каждый элемент встречается не более чем в множествах, то решение, приближающее оптимальное значение с точностью до фактора , может быть найдено за полиномиальное время с использованием LP-релаксации. Если ограничение заменяется на для всех в целочисленной линейной программе, представленной выше, то она превращается в (нецелочисленную) линейную программу. Алгоритм можно описать следующим образом:
Найдите оптимальное решение для программы , используя какой-либо полиномиальный метод решения линейных программ. Выберите все множества , для которых соответствующая переменная в решении имеет значение не менее 1/.
Find an optimal solution for the program using some polynomial time method of solving linear programs. Pick all sets for which the corresponding variable has value at least 1/ in the solution .
Результаты не приблизительности
Когда речь заходит об оценке размера вселенной, было показано, что задача о покрытии множествами не может быть аппроксимирована в полиномиальное время с точностью до фактора , если только класс NP не содержит квазиполиномиальных алгоритмов. Файге (1998) улучшил эту нижнюю границу до , при тех же предположениях, что практически соответствует коэффициенту аппроксимации, достигаемому жадным алгоритмом. установил нижнюю границу , где – некоторая константа, при более слабом предположении, что P ≠ NP. Недавно аналогичный результат с большим значением был доказан, а показал оптимальную неаппроксимируемость, доказав, что задачу нельзя аппроксимировать с точностью до , если P ≠ NP.
of , where is a certain constant, under the weaker assumption that PNP. A similar result with a higher value of was recently proved by showed optimal inapproximability by proving that it cannot be approximated to unless PNP.
Взвешенная крышка набора
Расслабляя целочисленную линейную программу для задачи покрытия множеств с весами, описанной выше, можно использовать рандомизированное округление для получения аппроксимации с коэффициентом [фактором]. Невесовую задачу покрытия множеств можно адаптировать к случаю с весами.