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

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

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

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

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