Аноним

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

Материал из WEGA
м
Строка 18: Строка 18:




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


== Нотация ==
== Нотация ==
4551

правка