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

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

В базах данных, которые использовали Руф и Шобель [8], матрицы представлены столбцовыми индексами первой и последней единицами в ее блоках последовательных единиц. Для таких матричных представлений было предложено правило быстрой редукции данных [8], которое устраняет «лишние» столбцы и в конкретных реализациях заменяет правило доминирования для столбцов. Новое правило работает быстрее, чем правило доминирования для столбцов (редукция матрицы по новому правилу может быть выполнена за время O(mn)), однако оно является менее мощным: в результате редукции матрицы A с использованием нового правила может получиться матрица с большим числом столбцов, чем в результате ее редукции по правилу доминирования для столбцов.

Руф и Шобель [8] представляют алгоритм на основе метода ветвей и границ для экземпляров задачи SET COVER, среднее количество блоков последовательных единиц в строке у которых невелико.