Gibt es einen Konstanten-Faktor-Approximationsalgorithmus für das Farbproblem von 2D-Rechtecken?

Das Problem, das wir hier betrachten, ist die Erweiterung des bekannten Intervallfarbproblems. Anstelle von Intervallen betrachten wir Rechtecke mit achsenparallelen Seiten. Ziel ist es, die Rechtecke mit einer minimalen Anzahl von Farben so einzufärben, dass zwei überlappenden Rechtecken unterschiedliche Farben zugewiesen werden.

Dieses Problem ist bekanntermaßen NP-hart. Xin Han, Kazuo Iwama, Rolf Klein und Andrezej Lingas (Approximation der maximalen unabhängigen Menge und der minimalen Scheitelpunktfärbung auf Box-Diagrammen) gaben eine O (log n) -Näherung. Gibt es einen besseren Näherungsalgorithmus?

Wir wissen, dass das Problem der Intervallfärbung in der Polynomzeit durch den First-Fit-Algorithmus gelöst wird, indem Intervalle entsprechend ihren linken Endpunkten betrachtet werden. Der First-Fit-Online-Algorithmus ist jedoch 8-kompetitiv, wenn die Intervalle in willkürlicher Reihenfolge angezeigt werden.

Was ist die Leistung des First-Fit-Algorithmus für das Problem der Rechteckfärbung? Was passiert mit dem First-Fit-Algorithmus, wenn die Rechtecke entsprechend ihrer linken (vertikalen) Seite angezeigt werden?

Vielen Dank im Voraus für jede Hilfe.

Wie die andere Antwort andeutet, ist die untere Grenze von $\Omega(\log n)$ nicht zu schwer zu erkennen. Lassen Sie uns das Kehren von unten mit einer horizontalen Linie durchführen. Die Idee ist, Komponenten zu bauen, die eine immer größere Anzahl von Farben erfordern. Insbesondere sei $C(i)$ ein Gadget, das ein oberes Rechteck mit der Farbe $i$ (dh die erste Anpassung würde ihm die Farbe $i$ zuweisen ). Es ist klar, dass $C(1)$ nur ein einzelnes Rechteck ist. Die Komponente $C(2)$ ist

$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)$

Soweit ich weiß, ist dies nicht bekannt. Ein altes Papier von Asplund und Grunbaum (1960) zeigt, dass wenn die Clique-Nummer 2 ist, die chromatische Nummer höchstens 6 ist (und das ist eng). Ich denke, es sollte einfach sein, Beispiele zu finden, bei denen die Lücke für die Erstanpassung größer als jede Konstante ist, da Bäume durch Schnittgraphen von Rechtecken dargestellt werden können und Bäume mit jedem Online-Algorithmus log n -Farben benötigen.

Ich denke, die Arbeiten von Asplund, Grunbaum oder später zeigen auch, dass die chromatische Anzahl der Rechteckschnittgraphen höchstens O (k ^ 2) beträgt, wobei k die Größe der maximalen Clique ist ... es sind jedoch keine bekannt Beispiele, die mehr als eine lineare Anzahl von Farben in k erfordern.