4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 01:48, 29 января 2021
, 29 января 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [ 7. Напротив, с точки зрения Руфа и Шобель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты. | Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Наличие свойства «почти С1Р» означает, что соответствующие матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, и случайным образом заменяя определенный процент единиц на нули [7]. Напротив, с точки зрения Руфа и Шобель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты. | ||
== Нотация == | == Нотация == | ||