Онлайн-алгоритм раскраски интервалов: различия между версиями

В работе Кирстеда и Троттера [ ] представлено решение задачи онлайн-раскраски интервалов. Авторы показали, что наилучший возможный коэффициент конкурентоспособности равен 3, и он достигается разработанным ими алгоритмом. Более точно, в статье доказана следующая теорема.

Теорема 1. Пусть имеется граф интервалов, который выдается в режиме онлайн вместе с его реализацией. Любой онлайновый алгоритм использует не менее 3! - 2 цвета для раскраски графа, и существует алгоритм, который достигает этой границы.

В продолжении статьи описываются алгоритм и построение нижней границы. Отметим, что алгоритму не нужно знать ! заранее. Более того, несмотря на то, что алгоритм детерминированный, в [12] было показано, что нижняя граница 3 коэффициента конкурентоспособности онлайн-алгоритмов для раскраски интервалов справедлива и для рандомизированных алгоритмов. Таким образом, [11] дает полное решение данной задачи.

Основная идея алгоритма заключается в создании «уровней». В момент поступления интервала он распределяется на уровень следующим образом. Обозначим через Ak объединение множеств интервалов, которые в данный момент принадлежат всем уровням 1, …, k. Интервалы распределяются так, чтобы клика наибольшей кардинальности в Ak имела размер k. Таким образом, A1 – это просто множество непересекающихся интервалов. При поступлении интервала алгоритм находит наименьшее k, такое, что новый интервал может присоединиться к уровню k, не нарушая вышеприведенного правила. Можно показать, что каждый уровень может быть раскрашен двумя цветами с помощью оффлайнового алгоритма. Поскольку определенный здесь алгоритм является онлайновым, такая раскраска не может быть найдена в общем случае (см. пример выше). Однако в работе [ ] было показано, что для каждого такого уровня требуется не более трех цветов, и раскраска, использующая три цвета, может быть найдена путем применения подхода First Fit к каждому уровню (с различными наборами цветов). Более того, первый уровень всегда можно раскрасить одним цветом, а ! в точности равно количеству уровней. Таким образом, всего используется не более 3! - 2 цветов.

Далее кратко описывается нижняя граница для детерминированного алгоритма. Идея заключается в создании уровней, как в предыдущем алгоритме. Уровни называются фазами. Каждая фаза увеличивает размер наибольшей клики на 1, пока не будет достигнуто значение !. Кроме того, каждая фаза (кроме первой) увеличивает количество цветов, используемых алгоритмом, на 3.

После создания каждой фазы некоторые участки прямой сжимаются в отдельные точки. Пусть дана точка p, являющаяся результатом сжатия интервала [a, b]. Каждый представленный в прошлом интервал, содержащийся в [a, b], также сжимается в p, и поэтому такая точка наследует список цветов, который не может получить ни один содержащий ее интервал. Это сделано для простоты доказательства и означает, что для данной точки p, которая является результатом сжатия, либо содержатся все интервалы, которые были сжаты в эту точку, либо она не пересекается ни с одним из них.

Построение последовательности прекращается, как только будет использовано 3! -2 цветов. Поэтому можно предположить, что задана начальная палитра из 3! - 3 цветов, причем все эти цвета могут быть использованы алгоритмом. i-й использованный цвет называется цветом номер i. Как только будет использован цвет 3! - 2 (даже если это происходит до завершения построения), оно прекращается. Построенная входная последовательность имеет наибольшую клику размером (не более) !.

Последовательность начинается с введения достаточно большого числа интервалов N; это фаза 0. Поскольку алгоритм использует не более 3! - 3 цветов, это означает, что существует множество N/(3a>-3) интервалов, имеющих один и тот же цвет. Все интервалы сжимаются в отдельные точки. Последующие фазы приводят к появлению дополнительных точек.