Apakah ada algoritma pendekatan faktor konstan untuk masalah pewarnaan persegi panjang 2D?

Masalah yang kami pertimbangkan di sini adalah perpanjangan dari masalah pewarnaan interval yang terkenal. Alih-alih interval kami menganggap persegi panjang memiliki sisi yang sejajar dengan sumbu. Tujuannya adalah untuk mewarnai persegi panjang menggunakan jumlah warna minimum sehingga setiap dua persegi panjang yang tumpang tindih diberi warna yang berbeda.

Masalah ini dikenal sebagai NP-hard. Xin Han, Kazuo Iwama, Rolf Klein dan Andrezej Lingas (Mendekati Set Independen Maksimum dan Pewarnaan Vertex Minimum pada Grafik Kotak) memberikan perkiraan O (log n). Apakah ada algoritma aproksimasi yang lebih baik?

Kita tahu bahwa masalah pewarnaan interval diselesaikan dalam waktu polinomial dengan algoritma first-fit dengan mempertimbangkan interval sesuai dengan titik akhir kiri mereka. Namun, algoritma online pertama-fit adalah 8-kompetitif ketika interval muncul dalam urutan sewenang-wenang.

Apa kinerja algoritma fit-pertama untuk masalah pewarnaan persegi panjang? Apa yang terjadi pada algoritma first-fit ketika persegi panjang muncul sesuai dengan sisi kiri (vertikal) mereka?

Terima kasih sebelumnya atas bantuannya.

Seperti yang disarankan oleh jawaban lain, $\Omega(\log n)$ batas bawah tidak terlalu sulit untuk dilihat. Mari kita lakukan sweeping bottom up dengan garis horizontal. Idenya adalah untuk membangun komponen yang membutuhkan jumlah warna yang lebih besar dan lebih besar. Secara khusus, biarkan $C(i)$ menjadi gadget yang memiliki persegi panjang atas dengan warna $i$ (yaitu, fit pertama akan menetapkannya warna $i$ ). Jelas, $C(1)$ hanyalah sebuah persegi panjang tunggal. Komponen $C(2)$ adalah

Secara umum, komponen $C(k)$ adalah persegi panjang dengan $C(1), \ldots, C(k-1)$ tergantung di bawahnya:

Sekarang, mudah untuk memverifikasi bahwa algoritma fit-first dengan sapuan horizontal dari bawah akan menggunakan warna $k$ untuk warna $C(k)$ . Namun, grafik persimpangan $C(k)$ hanya sebatang pohon, dan dapat diwarnai dengan $2$ warna. Sekarang, $C(k)$ hanyalah sebuah pohon Fibonacci dalam struktur, dan jumlah simpul di dalamnya adalah $2^{O(k)}$ , yang menyiratkan $\Omega( \log n )$ kesenjangan.

Karena ada algoritma sederhana yang mendapatkan perkiraan $O( \log n)$ untuk pewarnaan persegi panjang, ini mungkin ketat. Saya tidak tahu

Sejauh yang saya tahu, ini tidak diketahui. Sebuah kertas Asplund dan Grunbaum (1960-an) yang lama menunjukkan bahwa jika angka klik adalah 2, maka angka kromatik paling banyak adalah 6 (dan ini ketat). Saya pikir itu harus mudah untuk datang dengan contoh-contoh di mana kesenjangan untuk pertama-fit lebih besar daripada konstanta, karena pohon dapat diwakili oleh grafik persimpangan persegi panjang, dan pohon memerlukan log n warna dengan algoritma online.

Saya pikir Asplund, kertas Grunbaum, atau kertas yang lebih baru juga menunjukkan bahwa jumlah grafik persimpangan persegi kromatik adalah paling banyak O (k ^ 2), di mana k adalah ukuran klik maksimum ... namun, tidak ada yang diketahui contoh yang membutuhkan lebih dari linear dalam jumlah k warna.