Cover Image

On the FirstFit Algorithm for Online Unit-Interval Coloring

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Krekelberg, Bob, Liu, Alison Hsiang-Hsuan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Firefighting on Cactus Graphs
by: Hugen, Max, et al.
Published: (2025)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

Online Coloring of Short Intervals
by: Chybowska-Sokół, Joanna, et al.
Published: (2018)

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
by: Honorato-Droguett, Nicolás, et al.
Published: (2023)

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

Risk-Sensitive Online Algorithms
by: Christianson, Nicolas, et al.
Published: (2024)

Online Coloring for Graphs of Large Odd Girth
by: Yoneda, Hirotaka, et al.
Published: (2026)

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Online Algorithms with Randomly Infused Advice
by: Emek, Yuval, et al.
Published: (2023)

Coloring tournaments with few colors: Algorithms and complexity
by: Klingelhoefer, Felix, et al.
Published: (2023)

Online Interval Scheduling with Predictions
by: Boyar, Joan, et al.
Published: (2023)

An Empirical Study of Online Packet Scheduling Algorithms
by: Sakr, Nourhan, et al.
Published: (2016)

Dynamic Pricing Algorithms for Online Set Cover
by: Bender, Max, et al.
Published: (2024)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Tree Search With Predictions
by: Dinitz, Michael, et al.
Published: (2026)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Interval Selection with Binary Predictions
by: Karavasilis, Christodoulos
Published: (2025)

Exactly Hittable Interval Graphs
by: Dhannya, S. M., et al.
Published: (2023)

Interval Selection in Sliding Windows
by: Alexandru, Cezar-Mihail, et al.
Published: (2024)

Random-Order Interval Selection
by: Borodin, Allan, et al.
Published: (2024)

Near-optimal Algorithms for Stochastic Online Bin Packing
by: Ayyadevara, Nikhil, et al.
Published: (2022)

Algorithms for Efficient, Compact Online Data Stream Curation
by: Moreno, Matthew Andres, et al.
Published: (2024)

Computational Complexity of the Interval Ordering Problem
by: Pawlowski, Simeon, et al.
Published: (2026)

Investigations on Algorithm Selection for Interval-Based Coding Methods
by: Strutz, Tilo, et al.
Published: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
by: Kalavas, Andreas, et al.
Published: (2025)

Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
by: Arndt, Stephen, et al.
Published: (2026)

Hitting Geodesic Intervals in Structurally Restricted Graphs
by: Gima, Tatsuya, et al.
Published: (2025)

Interval-Constrained Bipartite Matching over Time
by: Abels, Andreas, et al.
Published: (2024)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)