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

17

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.

Soumitra
źródło

Odpowiedzi:

12

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Ω(logn)do(ja)jajado(1)do(2))

Ogólnie rzecz biorąc, komponent jest prostokątem z zwisającymi poniżej:do(k)do(1),,do(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ę .kdo(k)do(k)2)do(k)2)O(k)Ω(logn)

Ponieważ istnieje prosty algorytm, który pobiera przybliżenie do barwienia prostokątów, może być ciasno. Nie wiemO(logn)

Sariel Har-Peled
źródło
6

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.

ipsofacto
źródło
3

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.

ipsofacto
źródło