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

Пусть дан экземпляр (A, w) задачи SET COVER. Обозначим за R множество строк матрицы A, а за C – множество ее столбцов. Столбец cj охватывает строку ri, что обозначается ri 2 cj, если ai, j = 1.

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

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