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

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