Спасибо Вам большое за развернутый комментарий! Вы совершенно правы. Переход от вершинных раскрасок к расписанию не совсем корректен.
Заметим при этом, что решение дефектной раскраски находит допустимое решение для расписания. Интересно было бы узнать, насколько сильно оптимальное решение задачи расписания может отличаться от оптимального решения задачи дефектной раскраски. Так, например, если в вашем примере аналогично добавлять пары сервер-пользователь, то дефектная раскраска всегда будет состоять из двух цветов, а расписание - всегда из одного слота. То есть разрыв в 2 раза. Может ли получится больше?
Мы проверили этот же момент и для реберных раскрасок. Там задача расписания формулируется иначе (см. алгоритм размножения серверов). Сведение в этом случае корректное с двух сторон. Спасибо!
Добрый день!
Спасибо Вам большое за развернутый комментарий!
Вы совершенно правы. Переход от вершинных раскрасок к расписанию не совсем корректен.
Заметим при этом, что решение дефектной раскраски находит допустимое решение для расписания. Интересно было бы узнать, насколько сильно оптимальное решение задачи расписания может отличаться от оптимального решения задачи дефектной раскраски. Так, например, если в вашем примере аналогично добавлять пары сервер-пользователь, то дефектная раскраска всегда будет состоять из двух цветов, а расписание - всегда из одного слота. То есть разрыв в 2 раза. Может ли получится больше?
Мы проверили этот же момент и для реберных раскрасок. Там задача расписания формулируется иначе (см. алгоритм размножения серверов). Сведение в этом случае корректное с двух сторон. Спасибо!