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

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

'''Усовершенствованное правило доминирования для столбцов:''' Пусть имеются два столбца <math>c_{j_1}, c_{j_2} \in C</math> и строка, которую покрывают оба столбца <math>c_{j_1}</math> и <math>c_{j_2}</math>, и если <math>w(c_{j_1}) \ge w(c_{j_2}) + \sum_{c \in X (c_{j_1}, c_{j_2}) w(c)}</math>, то <math>c_{j_1}</math> ''доминируется'' <math>\{ c_{j_2} \} \cup X(c_{j_1}, c_{j_2})</math>. Удалить столбец <math>c_{j_1}</math> из матрицы A.