标题： 关于在线单位区间着色的FirstFit算法 显示英文标题

标题： On the FirstFit Algorithm for Online Unit-Interval Coloring

摘要： 在本文中，我们研究了FirstFit算法在在线单位长度区间着色问题中的性能，其中区间可以是开区间或闭区间，这为进一步研究FirstFit的实际性能提供了帮助。 我们通过推广经典的邻域界限，开发了一种复杂的计数方法，该方法通过计算潜在的交集来限制FirstFit可以分配给区间的颜色。 在推广中，我们证明对于任何区间，存在一个与其相交的关键区间，这有助于减少对交集数量的高估，并进一步限制区间可以被分配的颜色。 技术挑战随之转化为识别这些保证计数有效性的关键区间。 利用这种新的机制来限制FirstFit可以分配给区间的颜色，我们提供了当所有区间具有整数端点时的紧致分析，即$2\omega$种颜色，并给出了一般情况下的上界$\lceil\frac{7}{3}\omega\rceil-2$种颜色，其中$\omega$是输入区间集合所需的最优颜色数。 显示英文摘要

摘要： In this paper, we study the performance of the FirstFit algorithm for the online unit-length intervals coloring problem where the intervals can be either open or closed, which serves a further investigation towards the actual performance of FirstFit. We develop a sophisticated counting method by generalizing the classic neighborhood bound, which limits the color FirstFit can assign an interval by counting the potential intersections. In the generalization, we show that for any interval, there is a critical interval intersecting it that can help reduce the overestimation of the number of intersections, and it further helps bound the color an interval can be assigned. The technical challenge then falls on identifying these critical intervals that guarantee the effectiveness of counting. Using this new mechanism for bounding the color that FirstFit can assign an interval, we provide a tight analysis of $2\omega$ colors when all intervals have integral endpoints and an upper bound of $\lceil\frac{7}{3}\omega\rceil-2$ colors for the general case, where $\omega$ is the optimal number of colors needed for the input set of intervals.