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

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

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