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

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

В дополнение к этим двум правилам, столбец <math>c_{j_1} \in C</math> может также доминироваться подмножеством <math>C' \subseteq C</math> столбцов вместо одного столбца: если имеется подмножество <math>C' \subseteq C</math> и <math>w(c_{j_1}) \ge \sum_{c \in C'} w(c)</math>, и <math>\forall r \in R: r \in c_{j_1}</math> влечет <math>(\exist c \in C': r \in c)</math>, удалить <math>c_{j_1}</math> из A. К сожалению, поиск доминирующего подмножества C' для заданного множества <math>c_{j_1}</math> является NP-сложной задачей. Мекке и Вагнер [7] представили ограниченный вариант обобщенного правила доминирования столбцов.