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.
źródło