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

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

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

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

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

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