On the FirstFit Algorithm for Online Unit-Interval Coloring
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910820305207296 |
|---|---|
| author | Krekelberg, Bob Liu, Alison Hsiang-Hsuan |
| author_facet | Krekelberg, Bob Liu, Alison Hsiang-Hsuan |
| contents | 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ω$ colors when all intervals have integral endpoints and an upper bound of $\lceil\frac{7}{3}ω\rceil-2$ colors for the general case, where $ω$ is the optimal number of colors needed for the input set of intervals. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06558 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the FirstFit Algorithm for Online Unit-Interval Coloring Krekelberg, Bob Liu, Alison Hsiang-Hsuan Data Structures and Algorithms 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ω$ colors when all intervals have integral endpoints and an upper bound of $\lceil\frac{7}{3}ω\rceil-2$ colors for the general case, where $ω$ is the optimal number of colors needed for the input set of intervals. |
| title | On the FirstFit Algorithm for Online Unit-Interval Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.06558 |