Note: 

LaTeX Abstract: 
In this paper we study the problem of frequency assignment in wireless cellular networks under the framework of \emph{conflictfree colorings}. Given the range space $(P, \mathcal{R})$, where $P$ is a small set of $n$ points
in $\Re^2$, one would like to color $P$ with the minimum number of colors such that $(P, \cR)$ is conflictfree. This problem has been studied in a series of recent works~\cite{ELRS02,HS03,FLMMPSSWW05}.
We continue this study with the following question: Given $P$, is it possible to add a few set of points $Q$ such that
$( P \cup Q, \cR)$ can be colored with fewer colors than $(P, \cR)$? When the range spaces are intervals in $\Re$ or discs in $\Re^2$, a negative answer follows from previous work~\cite{PT03}. Surprisingly, we answer this question
in the affirmative for the case of rectangle ranges. Our main result is that, given $P$, and any $\eps \geq 0$,
one can always add a set $Q$ of $O(n^{1\eps})$ points such that $P \cup Q$ can be conflictfree colored using $\tilde O( n^{\frac{3}{8} (1+\eps)} )$ colors.
Moreover, the set $Q$ and the conflictfree coloring can be computed in polynomial time. Our result is obtained by introducing a general probabilistic recoloring technique,
which we call \emph{quasiconflictfree} coloring, and which may be of independent interest. A further application of this technique is also given. 
Categories / Keywords: 

HyperLinks / References / URLs: 

Personal Comments: 

File Upload: 



Download
Access Level: 
Public 
