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

Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [7]. Напротив, с точки зрения Руфа и Шёбель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты.