A new lower bound for the on-line coloring of intervals with bandwidth

作者：Mikos Patryk^*

来源：Theoretical Computer Science, 2018, 708: 96-100.

DOI：10.1016/j.tcs.2017.10.029

• On-line coloring
• Interval graphs
• Weighted intervals

The on-line interval coloring and its variants are important combinatorial problems with many applications in network multiplexing, resource allocation and job scheduling. In this paper we present a new lower bound of 4.1626 for the asymptotic competitive ratio for the on-line coloring of intervals with bandwidth which improves the best known lower bound of 24/7. For the on-line coloring of unit intervals with bandwidth we improve the lower bound of 1.831 to 2.

• 出版日期2018-1-17