Existe-t-il un algorithme d'approximation à facteur constant pour le problème de coloration des rectangles 2D?

Le problème que nous considérons ici est l'extension du problème bien connu de coloration d'intervalle. Au lieu d'intervalles, nous considérons des rectangles ayant des côtés parallèles aux axes. L'objectif est de colorer les rectangles en utilisant un nombre minimum de couleurs de sorte que deux rectangles qui se chevauchent se voient attribuer des couleurs différentes.

Ce problème est connu pour être NP-difficile. Xin Han, Kazuo Iwama, Rolf Klein et Andrezej Lingas (approximation de l'ensemble indépendant maximum et coloration du sommet minimum sur les graphiques de boîte) ont donné une approximation O (log n). Existe-t-il un meilleur algorithme d'approximation?

Nous savons que le problème de coloration des intervalles est résolu en temps polynomial par un algorithme de premier ajustement en considérant les intervalles en fonction de leurs points d'extrémité gauche. Cependant, l'algorithme en ligne de premier ajustement est compétitif 8 lorsque les intervalles apparaissent dans un ordre arbitraire.

Quelles sont les performances de l'algorithme de premier ajustement pour le problème de coloration du rectangle? Qu'advient-il de l'algorithme de premier ajustement lorsque les rectangles apparaissent en fonction de leur côté gauche (vertical)?

Merci d'avance pour toute aide à ce sujet.

$\Omega(\log n)$$C(i)$$i$$i$$C(1)$$C(2)$

$C(k)$$C(1), \ldots, C(k-1)$

$k$$C(k)$$C(k)$$2$$C(k)$$2^{O(k)}$$\Omega( \log n )$

$O( \log n)$

Pour autant que je sache, cela n'est pas connu. Un vieux papier d'Asplund et Grunbaum (1960ish) montre que si le nombre de cliques est 2, alors le nombre chromatique est au plus 6 (et c'est serré). Je pense qu'il devrait être facile de trouver des exemples où l'écart pour le premier ajustement est plus grand que n'importe quelle constante, car les arbres peuvent être représentés par un graphique d'intersection de rectangles, et les arbres nécessitent des couleurs log n par n'importe quel algorithme en ligne.

Je pense que le papier Asplund, Grunbaum, ou des articles ultérieurs montrent également que le nombre chromatique des graphiques d'intersection rectangle est au plus O (k ^ 2), où k est la taille de la clique maximale ... cependant, il n'y a pas de connu exemples qui nécessitent plus que linéaire en k nombre de couleurs.