pipette
ENEnglish

Online Graph Coloring with Random Arrivals

Hirotaka Yoneda, Masataka Yoneda

PreprintDice ser un gran avance

En palabras de los autores

We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming and are known in advance, we present a randomized exponential-time algorithm that colors any -colorable graph on vertices with colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed , and is better than a known lower bound of colors under adversarial arrivals for all fixed . In addition, assuming is known in advance, we obtain a competitive ratio of . For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of for all fixed . Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

Resultado principalLimitación que admiten los autores

En palabras simples Resumen con IA

Los autores estudian la coloración de grafos en línea donde los vértices llegan en orden aleatorio. Presentan un algoritmo aleatorizado que colorea cualquier grafo k-coloreable con n vértices con O(k^3 log^2 k log^4 n) colores en expectativa. Este es el primer algoritmo de coloración en línea que usa un número polilogarítmico de colores para todo k fijo de al menos 3. Su algoritmo exponencial en línea logra una garantía de rendimiento más allá del umbral de NP-dureza para algoritmos de aproximación de tiempo polinomial.

Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale.

Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.