Comments 3
Вопрос вызывает самый первый шаг, где идет переход от расписания к раскраскам в графе конфликтов.
Да, в правильной раскраске (с дефектом не более d) ни один сервер не будет нагружен более чем на d, если разные цвета пускать ко всем серверам отдельно.
Но нет, правильное расписание может соответствовать и не правильной раскраске (более d соседей у какой-то вершины того же цвета). Потому что эти >d конфликтов могут быть размазаны по разным серверам.
Вот контрпример: d=2, 4 пользователя {1,2,3,4} и 3 сервера {a,b,c}. Пользователь 1 хочет все сервера 1->a 1->b 1->c, остальные пользователи 2-4 хотят только один свой сервер 2->a 3->b 4->c. В итоге каждый сервер требуется только двумя ползователями, поэтому можно их всех четырех пустить сразу. Но граф конфликтов будет "звездой": пользователь 1 конфликтует со всеми остальными пользователями: ребра 1-2, 1-3, 1-4. В раскраске одним цветом вы получите более чем 2-дефектную раскраску. Т.е. решая задачу раскраски вы меньше чем в 2 слота расписание не составите, а оно есть.
Таким образом, задачу раскрасок можно свести к расписанию, но расписания к раскраскам - нет.
Добрый день!
Спасибо Вам большое за развернутый комментарий!
Вы совершенно правы. Переход от вершинных раскрасок к расписанию не совсем корректен.
Заметим при этом, что решение дефектной раскраски находит допустимое решение для расписания. Интересно было бы узнать, насколько сильно оптимальное решение задачи расписания может отличаться от оптимального решения задачи дефектной раскраски. Так, например, если в вашем примере аналогично добавлять пары сервер-пользователь, то дефектная раскраска всегда будет состоять из двух цветов, а расписание - всегда из одного слота. То есть разрыв в 2 раза. Может ли получится больше?
Мы проверили этот же момент и для реберных раскрасок. Там задача расписания формулируется иначе (см. алгоритм размножения серверов). Сведение в этом случае корректное с двух сторон. Спасибо!
Может быть хуже в N/2 раз. Пусть у вас N пользователей и N(N-1)/2 серверов. Каждый сервер хочет своя уникальная пара пользователей. Каждый пользователь хочет N-1 серверов. D=2. Опять же, можно всех в один и тот же тайм-слот засунуть, ибо каждый сервер имеет лишь двух ползователей. Но граф для раскрасок будет кликой, и там надо будет не менее N/2 цветов.
Дефектные раскраски и расписания