A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model.

Bahman Bahmani, Aranyak Mehta, Rajeev Motwani

Browse the full SODA paper archive.