Coloring and Maximum Independent Set of Rectangles

In this paper, we consider two geometric optimization problems:

Rectangle Coloring

problem (

RCOL

) and

Maximum Independent Set of Rectangles

(

MISR

). In

RCOL

, we are given a collection of

n

rectangles in the plane where overlapping rectangles need to be colored differently, and the goal is to find a coloring using minimum number of colors. Let

q

be the maximum clique size of the instance, i.e. the maximum number of rectangles containing the same point. We are interested in bounding the ratio

σ

(

q

) between the total number of colors used and the clique size. This problem was first raised by graph theory community in 1960 when the ratio of

σ

(

q

) ≤ 

O

(

q

) was proved. Over decades, except for special cases, only the constant in front of

q

has been improved. In this paper, we present a new bound for

σ

(

q

) that significantly improves the known bounds for a broad class of instances.

The bound

σ

(

q

) has a strong connection with the integrality gap of natural LP relaxation for

MISR

, in which the input is a collection of rectangles where each rectangle is additionally associated with non-negative weight, and our objective is to find a maximum-weight independent set of rectangles.

MISR

has been studied extensively and has applications in various areas of computer science. Our new bounds for

RCOL

imply new approximation algorithms for a broad class of

MISR

, including (i)

O

(loglog

n

) approximation algorithm for unweighted

MISR

, matching the result by Chalermsook and Chuzhoy, and (ii)

O

(loglog

n

)-approximation algorithm for the

MISR

instances arising in the

Unsplittable Flow Problem

on paths. Our technique builds on and generalizes past works.