Просмотр кода страницы Онлайн-алгоритм раскраски интервалов

== Ключевые слова и синонимы ==
Экстремальная задача рекурсивной комбинаторики

== Постановка задачи ==
Онлайновая раскраска интервалов представляет собой задачу раскраски графа. В таких задачах вершины графа представляются последовательно одна за одной. Каждая вершина представляется по очереди, вместе со списком ее ребер в графе, которые инцидентны ранее представленным вершинам. Задача состоит в том, чтобы назначить вершинам цвета (которые без потери общности предполагаются неотрицательными целыми числами) так, чтобы две вершины, имеющие общее ребро, получили разные цвета, а общее количество используемых цветов (или, как вариант, наибольший индекс любого используемого цвета) было минимизировано. Наименьшее количество цветов, с помощью которого все еще можно раскрасить граф, называется хроматическим числом графа.


Задача раскраски интервалов определяется следующим образом. Интервалы на вещественной прямой представляются последовательно один за другим, и онлайновый алгоритм должен присвоить каждому интервалу цвет до появления следующего интервала таким образом, чтобы никакие два пересекающихся интервала не имели одинакового цвета. Цель также заключается в том, чтобы минимизировать количество цветов, используемых для раскраски интервалов. Последняя задача эквивалентна раскраске графов интервалов. Это графы, в представлении (или реализации) которых каждый интервал представляет вершину, а две вершины имеют общее ребро тогда и только тогда, когда интервалы пересекаются. Предполагается, что граф интервалов выдается в онлайновом режиме вместе с его реализацией.


Пусть задан граф интервалов. Обозначим за <math>\omega</math> размер клики наибольшей кардинальности (полного подграфа) в нем. Графы интервалов обладают тем особым свойством, что в реализации множество вершин клики имеет общую точку, в которой все они пересекаются.


Прежде чем обсуждать онлайн-задачу, необходимо указать некоторые свойства графов интервалов. Существует простой оффлайновый алгоритм, который производит оптимальную раскраску таких графов. Мы говорим, что алгоритм применяет подход First Fit, если каждый раз, когда ему нужно присвоить интервалу цвет, он назначает цвет с наименьшим индексом, который все еще позволяет получить допустимую раскраску. Оптимальный алгоритм просто рассматривает интервалы, отсортированные слева направо по их левым конечным точкам, и применяет подход First Fit. Заметим, что в результирующей раскраске никогда не используется более <math>\omega</math> цветов. И в самом деле, графы интервалов [[Совершенный_граф|совершенны]]. //''Граф <math>G</math> является совершенным, если любой его индуцированный подграф <math>G'</math> (включая <math>G</math>), может быть раскрашен с помощью <math>\omega(G')</math> цветов, где <math>\omega(G')</math> – размер клики наибольшей кардинальности в <math>G'</math>. (Для любого графа <math>\omega</math> является очевидной нижней границей его хроматического числа).''//


Однако, поскольку в онлайновой конфигурации интервалы появляются в произвольном порядке, разработать оптимальную раскраску невозможно. Рассмотрим простой пример, когда представляются два интервала [1, 3] и [6, 8]. Если они раскрашены двумя разными цветами, это уже неоптимально, так как можно использовать один и тот же цвет для обоих. Однако если последовательность интервалов дополняется элементами [2, 5] и [4, 7], то эти два новых интервала не могут получить цвет предыдущих интервалов или один и тот же цвет для обоих новых интервалов. Таким образом, используется три цвета, хотя можно разработать допустимую раскраску с использованием двух цветов. Заметим, что даже если заранее известно, что входные данные можно раскрасить ровно двумя цветами, незнание того, будут ли дополнительные интервалы такими, как определено выше, или вместо них поступит один интервал [2, 7], приводит к использованию трех цветов вместо всего двух.


Онлайновая раскраска обычно трудна, что относится и к некоторым простым классам графов, таким как деревья. Это связано с нижней границей <math>\Omega(log \; n)</math>, полученной Дьярфашем и Лехелем [9] для коэффициента конкурентоспособности онлайн-раскраски деревьев. Существует очень мало классов, для которых известны константные границы. Одним из таких классов являются линейные графы, для которых Бар-Ной, Мотвани и Наор [3] показали, что алгоритм First-Fit является 2-конкурентным (в частности, он использует не более <math>2 \cdot opt - 1</math> цветов, где OPT – количество цветов в оптимальной раскраске), и это наилучший возможный вариант. Позднее этот результат был обобщен до <math>k \cdot opt - k + 1</math> для графов без (k + 1)-клешней в [6] (заметим, что линейные графы являются графами без 3-клешней).

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


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


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


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


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


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


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


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


Далее определяется фаза <math>i < \omega</math>. Фазы строятся таким образом, чтобы в начале фазы <math>i</math> было достаточно большое количество точек, содержащих заданный набор из <math>3 i - 2</math> цветов (интересующие точки). Без потери общности предположим, что это цвета <math>1, ..., 3i - 2</math>, где размер наибольшей клики равен <math>i</math>. Существуют и другие точки, содержащие другие наборы <math>i</math> цветов или наборы не более <math>i - 1</math> цветов. Все эти точки называются пустыми точками. В это время интересующие точки разбиваются на последовательные множества по четыре.


Далее определяются некоторые дополнительные интервалы, увеличивающие размер наибольшей клики ровно на единицу. Пусть дано множество из четырех точек <math>a_1, a_2, a_3, a_4</math> и пусть <math>b</math> – самая левая пустая точка справа от <math>a_1</math>, между <math>a_1</math> и <math>a_2</math>. Если такой точки не существует, положим <math>b = (a_1 + a_2)/2</math>. Аналогично, пусть <math>c</math> – крайняя правая пустая точка между <math>a_3</math> и <math>a_4</math>, и если такой точки нет, положим <math>c = (a_3 + a_4)/2</math>. Пусть <math>d</math> – точка между <math>a_2</math> и <math>a_3</math>, не являющаяся пустой. Вводятся интервалы <math>I_1 = [a_1, (a_1 + b)/2]</math> и <math>I_2 = [(c + a_4)/2, a_4]</math>. Очевидно, что ни один из них не может получить один из используемых в настоящее время <math>3i - 2</math> цветов. Если они оба получат один и тот же новый цвет, то вводятся интервалы <math>I_3 = [(a_1 + b)/2, d]</math> и <math>I_4 = [d, (c + a_4)/2]</math>. Интервал <math>I_3</math> пересекается с <math>a_2</math> и с <math>I_1</math>. Поэтому он получает еще один дополнительный цвет. Второй интервал <math>I_4</math> пересекается с <math>I_3</math>, <math>a_3</math> и <math>I_2</math>. Поэтому ему присваивается третий новый цвет. Если <math>I_1</math> и <math>I_2</math> получают разные новые цвета, то вводится интервал <math>I_5 = [(a_1 + b)/2, (c + a_4)/2]</math>. Поскольку <math>I_5</math> пересекается с <math>I_1, I_2, a_2, a_3</math>, он должен получить третий новый цвет. Каждый такой интервал <math>[a_1, a_4]</math> сжимается в единственную точку, содержащую <math>3i + 1</math> цветов. Поскольку цветов меньше <math>3\omega</math>, а каждая точка использует ровно <math>3i + 1 < 3 \omega</math> из них, то таких вариантов меньше <math>(3 \omega)!</math> и можно выбрать достаточно большое число точек, имеющих одинаковый набор цветов. Точки, содержащие именно такой набор цветов, становятся интересными точками следующей фазы, а остальные – пустыми точками следующей фазы. Точки, которые являются пустыми точками предыдущих фаз и не содержатся в сжатых интервалах, остаются пустыми. Единственные точки, в которых пересекаются новые интервалы, – это точки, в которых не было предыдущих интервалов, поэтому размер клики увеличивается ровно на 1.


В это время может быть выполнена фаза <math>i + 1</math>. После фазы <math>\omega - 1</math> остается не менее <math>3 \omega -2</math> цветов; утверждение доказано. Заметим, что до этой фазы требуется минимальное число в четыре интересных точки.

== Применение ==
В этом разделе обсуждаются как реальные приложения данной задачи, так и применение методов Кирстеда и Троттера [11] к смежным задачам.


Множество вариантов применения приходится на различные сети связи. Потребность в подключениях во всем мире быстро растет. С другой стороны, сети по-прежнему состоят из очень дорогих компонентов. Поэтому для экономии средств требуется применение алгоритмов оптимизации.


Рассмотрим сеть с линейной топологией, состоящую из линий связи. Каждый запрос на соединение – это запрос на путь между двумя узлами сети. Набор запросов, назначенных каналу, должен состоять из непересекающихся путей. Цель заключается в том, чтобы минимизировать количество используемых каналов (цветов). Запрос на соединение между <math>a</math> и <math>b</math> соответствует интервалу <math>[a, b]</math>, и цель состоит в том, чтобы свести к минимуму количество каналов, необходимых для обслуживания всех запросов.


Еще один вариант применения, связанный с сетью, возникает, когда запросы имеют постоянную длительность <math>c</math>, и все запросы должны быть обслужены как можно быстрее. В этом случае цвета соответствуют временным интервалам, а общее количество цветов – длине расписания.


Это лишь примеры, задачу можно описать и как задачу составления расписания, а также она представляет теоретический интерес как естественная онлайновая задача раскраски графов.


Два более поздних исследования представляют возможный интерес как в связи с их релевантностью исходной проблеме, так и в связи с использованием соответствующих методов.


Варианты применения в сетях, упомянутые выше, поднимают более общую проблему, изучаемую в последние годы. В этих вариантах применения предполагается, что после удовлетворения запроса на соединение между двумя точками канал блокируется, по крайней мере, на время действия этого запроса. Интересный вопрос, поднятый Адами и Эрлебахом [1], заключается в следующем. Предположим, что запрос состоит не только из запрашиваемого интервала, но и из требования к пропускной способности; то есть клиент канала связи указывает, какой именно объем канала ему нужен. Таким образом, в некоторых случаях возможно перекрытие запросов, использующих один и тот же канал. Требуется, чтобы в каждый момент времени сумма всех требований к пропускной способности запросов с общим цветом не превышала значения 1, которое является пропускной способностью канала. Эта задача называется ''онлайновой раскраской интервалов с учетом пропускной способности''. В работе [1] для этой задачи был разработан алгоритм с (большим) константным коэффициентом конкурентоспособности. Изначальная задача раскраски интервалов является частным случаем этой задачи, когда все запросы на пропускную способность равны 1. Заметим, что эта задача также является обобщением [[Задача_об_упаковке_в_контейнеры|задачи об упаковке в контейнеры]], поскольку упаковка контейнеров – это частный случай задачи, когда все запросы имеют общую точку. Азар и др. [2] разработали для этой задачи алгоритм с коэффициентом конкурентоспособности не более 10. Для этого они разделили запросы на четыре класса в зависимости от требований к пропускной способности и раскрасили каждый такой класс отдельно. Класс запросов с пропускной способностью в <math>(\frac{1}{2}, 1]</math> был раскрашен с помощью базового алгоритма из [11], поскольку никакие два таких запроса, раскрашенных одним цветом, не могут пересекаться. Два других класса, а именно <math>(0, \frac{1}{4}]</math> и <math>(\frac{1}{4}, \frac{1}{2}]</math>, были раскрашены с помощью адаптированного алгоритма из [11]. Эпстайн и Леви [7, 8] разработали улучшенные нижние границы коэффициента конкурентоспособности, показав, что онлайновая раскраска интервалов с учетом пропускной способности сложнее, чем просто онлайновая раскраска интервалов.


Еще одна задача, связанная с раскраской, – это задача о ''максимальной раскраске''. В этой задаче каждому интервалу присваивается неотрицательный вес. Если задана раскраска, то весом цвета считается максимальный вес любой вершины этого цвета. Цель заключается в том, чтобы минимизировать сумму весов используемых цветов. Заметим, что если все веса равны 1, то задача о максимальной раскраске сводится к задаче раскраски графа. Пеммараджу, Раман и Варадараджан [13] исследовали ''оффлайновую'' задачу максимальной раскраски для графов интервалов. Они применили алгоритм, основанный на алгоритме из работы [11]. Таким образом, они сортируют интервалы в соответствии с их весами в монотонном невозрастающем порядке. Однако, поскольку их алгоритм не является онлайновым, они использовали указанное выше свойство, заключающееся в том, что каждый уровень на самом деле является 2-цветным и, таким образом, это приводит к оффлайновой 2-аппроксимации задачи о максимальной раскраске на графах интервалов.


Эпстайн и Левин [5] исследовали онлайновую задачу о максимальной раскраске на графах интервалов. Они разработали редукцию общего вида, позволяющую преобразовать алгоритмы для раскраски графов в алгоритмы для максимальной раскраски. Снижение коэффициента конкурентоспособности составляет мультипликативный коэффициент 4 для детерминированных и <math>e \approx 2,718</math> – для рандомизированных алгоритмов. Таким образом, используя алгоритм из [11] в качестве черного ящика, они получили 12-конкурентный детерминированный алгоритм и <math>3 \cdot e \approx 8,155</math>-конкурентный рандомизированный алгоритм. Другим результатом [5] является нижняя граница коэффициента конкурентоспособности любого рандомизированного алгоритма, равная 4.

== Открытые вопросы ==
Поскольку в работе [11] было найдено хорошее и чистое решение проблемы онлайновой раскраски интервалов, она не ставит прямых открытых вопросов. Тем не менее, одна связанная с ней проблема интересовала исследователей на протяжении последних тридцати лет – это производительность алгоритма First Fit в этой задаче. Кирстедом [10] было показано, что First Fit использует не более <math>40 \omega</math> цветов, что означает, что он имеет константный коэффициент конкурентоспособности. Однако точное его значение найти так и не удалось. Лучшими опубликованными на данный момент результатами являются верхняя граница в 10k, полученная в работе [13], и нижняя граница в 4,4k, полученная Хробаком и Слюсареком [4]. Более актуальную информацию об этом см. в [14]. Интересно отметить, что в задаче онлайновой раскраски интервалов с учетом пропускной способности алгоритм First Fit имеет неограниченный коэффициент конкурентоспособности [1].


Другим открытым вопросом является нахождение наилучших возможных коэффициентов конкурентоспособности для онлайновой раскраски интервалов с учетом пропускной способности и для максимальной раскраски графов интервалов. Как было отмечено выше, в настоящее время разрыв для раскраски с учетом пропускной способности составляет от <math>24/7 \approx 3,4286</math> согласно [7, 8] до 10 [2], а для максимальной раскраски – от 4 до 12 [5].

== Литература ==
1.	Adamy, U., Erlebach, T.: Online coloring of intervals with bandwidth. In: Proc. of the First International Workshop on Approximation and Online Algorithms (WAOA2003), pp. 1 -12 (2003)

2.	Azar, Y., Fiat, A., Levy, M., Narayanaswamy, N.S.: An improved algorithm for online coloring of intervals with bandwidth. Theor. Comput. Sci. 363(1), 18-27 (2006)

3.	Bar-Noy, A., Motwani, R., Naor, J.: The greedy algorithm is optimal for on-line edge coloring. Inf. Proc. Lett. 44(5), 251-253 (1992)

4.	Chrobak, M., Slusarek, M.: On some packing problems relating to dynamical storage allocation. RAIRO J. Inf. Theor. Appl. 22, 487^99(1988)

5.	Epstein, L., Levin, A.: On the max coloring problem. In: Proc. of the Fifth International Workshop on Approximation and Online Algorithms (WAOA2007) (2007), pp. 142-155

6.	Epstein, L., Levin, A., Woeginger, G.J.: Graph coloring with rejection. In: Proc. of 14th European Symposium on Algorithms (ESA2006), pp. 364-375. (2006)

7.	Epstein, L., Levy, M.: Online interval coloring and variants. In: Proc. of The 32nd International Colloquium on Automata, Languages and Programming (ICALP2005), pp. 602-613. (2005)

8.	Epstein, L., Levy, M.: Online interval coloring with packing constraints. In: Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS2005), pp. 295-307. (2005)

9. Gyarfas, A., Lehel, J.: Effective on-line coloring of P5-free graphs. Combinatorica 11(2), 181-184(1991)

10.	Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J.Discret. Math. 1(4), 526-530 (1988)

11.	Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congr. Numerantium 33,143-153 (1981)

12.	Leonardi, S., Vitaletti, A.: Randomized lower bounds for online path coloring. In: Proc. of the second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98), pp. 232-247. (1998)

13.	Pemmaraju, S., Raman, R., Varadarajan, K.: Buffer minimization using max-coloring. In: Proc. of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 562-571. (2004)

14.	Trotter, W.T.: Current research problems: First Fit colorings of interval graphs. http://www.math.gatech.edu/~trotter/rprob.htm Access date: December 24, 2007.