Online graph-coloring competitive-ratio conjectures
This entry tracks Online graph-coloring competitive-ratio conjectures.
The result establishes an asymptotic randomized-versus-deterministic separation against oblivious adversaries and substantially narrows the randomized gap.
Latest development
The authors prove an Ω(n/log n) deterministic lower bound, an O(n(log log n)^2/log^2 n) randomized upper bound, and an O(n/(log log n)^{2−ε}) deterministic upper bound.
Editorial caveat
The conjectured optimal randomized O(n/log^2 n) bound and the strongest deterministic lower-bound formulation remain open.
References
- Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms — arXiv — Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
Source: arXiv
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.