The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the rectangles using minimum number of colors such that any two overlapping rectangles are assigned different colors.
This problem is known to be NP-hard. Xin Han, Kazuo Iwama, Rolf Klein and Andrezej Lingas (Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs) gave an O(log n) approximation. Is there a better approximation algorithm?
We know that the interval coloring problem is solved in polynomial time by first-fit algorithm by considering intervals according to their left endpoints. However, first-fit online algorithm is 8-competitive when the intervals appear in arbitrary order.
What is the performance of the first-fit algorithm for the rectangle coloring problem? What happens to first-fit algorithm when the rectangles appear according to their left (vertical) sides?
Thanks in advance for any help on this.