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

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

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