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

В общем случае задача SET COVER является NP-сложной [4], однако она может быть решена за полиномиальное время для экземпляров, столбцы которых можно переставить таким образом, чтобы единицы в каждой строке появлялись последовательно – иначе говоря, для экземпляров, удовлетворяющих ''свойству последовательных единиц'' (C1P). ''//Свойство C1P может быть симметричным образом определено для столбцов, однако в данной статье рассматриваются строки. Задачу SET COVER над экземплярами со свойством C1P можно решить за полиномиальное время – например, при помощи подхода линейного программирования – поскольку соответствующие матрицы коэффициентов являются полностью унимодулярными

(см. [9])//''