Czy istnieje algorytm aproksymacji stałego współczynnika dla problemu kolorowania prostokąta 2D?

Problem, który rozważamy tutaj, to rozszerzenie znanego problemu kolorowania interwałów. Zamiast przedziałów uważamy prostokąty o bokach równoległych do osi. Celem jest pokolorowanie prostokątów przy użyciu minimalnej liczby kolorów, tak aby każdemu z dwóch nachodzących na siebie prostokątów przypisano różne kolory.

Ten problem jest znany jako trudny dla NP. Xin Han, Kazuo Iwama, Rolf Klein i Andrezej Lingas (Przybliżenie maksymalnego niezależnego zestawu i minimalnego zabarwienia wierzchołków na wykresach pudełkowych) dali przybliżenie O (log n). Czy istnieje lepszy algorytm aproksymacyjny?

Wiemy, że problem kolorowania interwałów rozwiązuje się w czasie wielomianowym za pomocą algorytmu pierwszego dopasowania, biorąc pod uwagę interwały zgodnie z ich lewymi punktami końcowymi. Jednak algorytm online pierwszego dopasowania jest 8-konkurencyjny, gdy interwały pojawiają się w dowolnej kolejności.

Jaka jest wydajność algorytmu pierwszego dopasowania dla problemu kolorowania prostokąta? Co dzieje się z algorytmem pierwszego dopasowania, gdy prostokąty pojawiają się zgodnie z ich lewymi (pionowymi) bokami?

Z góry dziękuję za wszelką pomoc w tym zakresie.

Jak sugeruje druga odpowiedź, dolna granica nie jest zbyt trudna do zobaczenia. Zróbmy teraz zamiatanie od dołu poziomą linią. Chodzi o to, aby budować komponenty wymagające coraz większej liczby kolorów. W szczególności niech będzie gadżetem, który ma górny prostokąt w kolorze (tj. Pierwsze dopasowanie przypisałoby mu kolor ). Oczywiście jest tylko pojedynczym prostokątem. Składnikiem jest$\Omega(\log n)$$C(i)$$i$$i$$C(1)$$C(2)$

Ogólnie rzecz biorąc, komponent jest prostokątem z zwisającymi poniżej:$C(k)$$C(1), \ldots, C(k-1)$

Teraz łatwo jest zweryfikować, że algorytm dopasowania pierwszego z zamiataniem w poziomie od dołu użyłby kolorów do koloru . Jednak wykres przecięcia jest tylko drzewem i może być pokolorowany kolorami. Teraz jest po prostu drzewem Fibonacciego w strukturze, a zatem liczba zawartych w nim węzłów wynosi , co implikuje lukę .$k$$C(k)$$C(k)$$2$$C(k)$$2^{O(k)}$$\Omega( \log n )$

Ponieważ istnieje prosty algorytm, który pobiera przybliżenie do barwienia prostokątów, może być ciasno. Nie wiem$O( \log n)$

O ile mi wiadomo, nie jest to znane. Stary papier Asplunda i Grunbauma (1960ish) pokazuje, że jeśli liczba kliki wynosi 2, to liczba chromatyczna wynosi co najwyżej 6 (i jest ciasno). Myślę, że powinno być łatwo wymyślić przykłady, w których przerwa w pierwszym dopasowaniu jest większa niż jakakolwiek stała, ponieważ drzewa mogą być reprezentowane przez wykres przecięcia prostokątów, a drzewa wymagają log n kolorów przez dowolny algorytm online.

Sądzę, że papier Asplunda, Grunbauma lub późniejszy pokazują również, że liczba chromatyczna wykresów przecięcia prostokąta wynosi co najwyżej O (k ^ 2), gdzie k jest rozmiarem maksymalnej kliki ... jednak nie są znane przykłady wymagające więcej niż liniowej liczby k kolorów.