El problema que consideramos aquí es la extensión del conocido problema de coloreado de intervalos. En lugar de intervalos, consideramos rectángulos que tienen lados paralelos a los ejes. El objetivo es colorear los rectángulos usando un número mínimo de colores, de modo que a cualquiera de los dos rectángulos superpuestos se les asignen colores diferentes.
Se sabe que este problema es NP-hard. Xin Han, Kazuo Iwama, Rolf Klein y Andrezej Lingas (Aproximación del conjunto independiente máximo y coloración mínima del vértice en los gráficos de caja) dieron una aproximación O (log n). ¿Existe un mejor algoritmo de aproximación?
Sabemos que el problema de coloreado de intervalos se resuelve en tiempo polinómico mediante un algoritmo de primer ajuste al considerar los intervalos de acuerdo con sus puntos finales izquierdos. Sin embargo, el algoritmo en línea de primer ajuste es 8 competitivo cuando los intervalos aparecen en orden arbitrario.
¿Cuál es el rendimiento del algoritmo de primer ajuste para el problema de coloración del rectángulo? ¿Qué sucede con el algoritmo de primer ajuste cuando los rectángulos aparecen de acuerdo con sus lados izquierdos (verticales)?
Gracias de antemano por cualquier ayuda en esto.