Покрытие множества почти последовательными подмножествами

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

Множество представителей

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

Задача покрытия множества SET COVER получает на вход множество R, состоящее из m элементов, множество C из n подмножеств R и весовую функцию [math]\displaystyle{ w: C \to \mathbb{Q} }[/math]. Задача заключается в выборе подмножеств [math]\displaystyle{ C' \subseteq C }[/math] с минимальным весом, объединение которых содержит все элементы R.

Множества R и C могут быть представлены в виде бинарной матрицы A размера m x n, включающей строку для каждого элемента в R и столбец для каждого подмножества R в C, где значение ячейки [math]\displaystyle{ a_{i, j} }[/math] равно 1 в случае, если i-й элемент R является частью j-го подмножества C. Таким образом, задачу SET COVER можно сформулировать следующим образом.

Дано: бинарная матрица A размера m x n и весовая функция w над столбцами A.

Требуется: выбрать некоторые столбцы A с минимальным весом так, чтобы подматрица A' матрицы A, порождаемая этими столбцами, имела по крайней мере одно значение 1 в каждой строке.

В общем случае задача SET COVER является NP-сложной [4], однако она может быть решена за полиномиальное время для экземпляров, столбцы которых можно переставить таким образом, чтобы единицы в каждой строке появлялись последовательно – иначе говоря, для экземпляров, удовлетворяющих свойству последовательных единиц (C1P). [Свойство C1P может быть симметричным образом определено для столбцов, однако в данной статье рассматриваются строки. Задачу SET COVER над экземплярами со свойством C1P можно решить за полиномиальное время – например, при помощи подхода линейного программирования – поскольку соответствующие матрицы коэффициентов являются полностью унимодулярными (см. [9])]

Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [7]. Напротив, с точки зрения Руфа и Шобель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты.

Нотация

Пусть дан экземпляр (A, w) задачи SET COVER. Обозначим за R множество строк матрицы A, а за C – множество ее столбцов. Столбец [math]\displaystyle{ c_j }[/math] охватывает строку [math]\displaystyle{ r_i }[/math], что обозначается [math]\displaystyle{ r_i \in c_j }[/math], если [math]\displaystyle{ a_{i, j} = 1 }[/math].

Бинарная матрица обладает сильным свойством C1P, если (без какой-либо перестановки столбцов) единицы появляются последовательно в каждой строке. Блок последовательных единиц является максимальной последовательностью единиц в строке. Возможно за линейное время определить, обладает ли матрица свойством C1P, и если да, то вычислить перестановку столбцов, в результате которой получается сильное свойство C1P [2, 3, 6]. Однако заметим, что перестановка столбцов бинарной матрицы таким образом, чтобы количество блоков последовательных единиц в полученной матрице было минимальным, является NP-сложной [1, 4, 5].

Правило редукции данных за полиномиальное время преобразует заданный экземпляр I задачи оптимизации в экземпляр I той же задачи таким образом, что |I'| < |I|, и оптимальное решение для I имеет то же значение (например, вес), что и оптимальное решение для I. При наличии набора правил редукции данных процесс редуцирования экземпляра задачи заключается в многократном применении правил до тех пор, пока не останется других возможностей применения правил; полученный в результате экземпляр называется редуцированным.

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

Правила редукции данных

Для задачи SET COVER существуют хорошо известные правила редукции данных:

Правило доминирования для строк: если имеются две строки [math]\displaystyle{ r_{i_1}, r_{i_2} \in R }[/math] и [math]\displaystyle{ \forall c \in C: r_{i_1} \in c }[/math] влечет [math]\displaystyle{ r_{i_2} \in c }[/math], то [math]\displaystyle{ r_{i_1} }[/math] доминирует [math]\displaystyle{ r_{i_2} }[/math] (или, что то же самое, [math]\displaystyle{ r_{i_2} }[/math] доминируется [math]\displaystyle{ r_{i_1} }[/math]). Удалить строку [math]\displaystyle{ r_{i_2} }[/math] из матрицы A.

Правило доминирования для столбцов: если имеются два столбца cj1;cj2 2 C, W(CJ1) > W(CJ2), и 8r 2 R: r 2 cj1 влечет r 2 cj2, то cj2 доминирует cj1. Удалить столбец cj из матрицы A.

В дополнение к этим двум правилам, столбец cj € С может также доминироваться подмножеством C0 С C столбцов вместо одного столбца: если имеется подмножество C'CC и w(cj1) — Pc2C0 w(c) и 8r 2 R: r 2 cj1 влечет (9c 2 C0: r 2 c), удалить cj1 из A. К сожалению, поиск доминирующего подмножества C0 для заданного множества cj1 является NP-сложной задачей. Мекке и Вагнер [ ] представили ограниченный вариант обобщенного правила доминирования столбцов.

Для каждой строки r 2 R обозначим за cmin(r) столбец в C, который покрывает r и имеет минимальный вес при соблюдении этого свойства. Для двух столбцов cj1;cj2 2 C определим X(cj1;cj2) := fcmin(r) j r 2 cj 1 г ^ cj2 g. Новое правило редукции данных будет выглядеть следующим образом.

Усовершенствованное правило доминирования для столбцов: Пусть имеются два столбца cj1, cj2 2 C и строка, которую покрывают оба столбца cj1 and cj2, и если w(cj1) > w(cj2), то cj1 доминируется FCJ2G [ X(CJ1; cj2). Удалить столбец cj1 из матрицы A.

Теорема 1 [7]. Приведение матрицы A может быть выполнено за время O(Nn) в соответствии с правилом доминирования для столбцов, за время O(Nm) в соответствии с правилом доминирования для строк и за время O(Nmn) в соответствии со всеми тремя описанными выше правилами доминирования, где N – количество единиц в матрице A.

В базах данных, которые использовали Руф и Шобель [ ], матрицы представлены столбцовыми индексами первой и последней единицами в ее блоках последовательных единиц. Для таких матричных представлений было предложено правило быстрой редукции данных [8], которое устраняет «лишние» столбцы и в конкретных реализациях заменяет правило доминирования для столбцов. Новое правило работает быстрее, чем правило доминирования для столбцов (приведение матрицы по новому правилу может быть выполнено за время O(mn)), однако оно является менее мощным: в результате приведения матрицы A с использованием нового правила может получиться матрица с большим числом столбцов, чем в результате приведения A по правилу доминирования для столбцов.

Алгоритмы

Мекке и Вагнер [ ] представили алгоритм, который решает задачу SET COVER, перечисляя все допустимые решения.