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

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