Abstract:

Motivated by a frequency assignment problem in cellular networks, we
introduce and study a new coloring problem that we call \emph{Minimum
  Conflict-Free Coloring} (Min-CF-Coloring).  In its general form, the
input of the Min-CF-coloring problem is a set system $(X,\Scal)$,
where each $S \in \Scal$ is a subset of $X$. The output is a coloring
$\chi$ of the sets in $\Scal$ that satisfies the following constraint:
for every $x \in X$ there exists a color $i$ and a unique set $S \in
\Scal$, such that $x \in S$ and $\chi(S) = i$.  The goal is to
minimize the number of colors used by the coloring $\chi$.

Min-CF-coloring of general set systems is not easier than the classic
graph coloring problem.  However, in view of our motivation, we
consider set systems induced by simple geometric regions in the plane.
In particular, we study disks (both congruent and non-congruent),
axis-parallel rectangles (with a constant ratio between the smallest
and largest rectangle), regular hexagons (with a constant ratio between
the smallest and largest hexagon), and general congruent
centrally-symmetric convex regions in the plane. In all cases we have
coloring algorithms that use $O(\log n)$ colors (where $n$ is the
number of regions).  For rectangles and hexagons we obtain a
constant-ratio approximation algorithm when the ratio between the
largest and smallest rectangle (hexagon) is constant.  We also show
that, even in the case of unit disks, $\Theta(\log n)$ colors may be
necessary.  

This paper will be presented in FOCS 2002.
Joint work with Zvi Lotker, Dana Ron, and Shakhar Smorodinsky.