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

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

Варианты применения в сетях, упомянутые выше, поднимают более общую проблему, изучаемую в последние годы. В этих вариантах применения предполагается, что после удовлетворения запроса на соединение между двумя точками канал блокируется, по крайней мере, на время действия этого запроса. Интересный вопрос, поднятый Адами и Эрлебахом [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] разработали улучшенные нижние границы коэффициента конкурентоспособности, показав, что онлайновая раскраска интервалов с учетом пропускной способности сложнее, чем просто онлайновая раскраска интервалов.