Note: |
|
LaTeX Abstract: |
In this paper we study the problem of frequency assignment in wireless cellular networks under the framework of \emph{conflict-free 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 conflict-free. 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 conflict-free colored using $\tilde O( n^{\frac{3}{8} (1+\eps)} )$ colors.
Moreover, the set $Q$ and the conflict-free coloring can be computed in polynomial time. Our result is obtained by introducing a general probabilistic re-coloring technique,
which we call \emph{quasi-conflict-free} 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 |
|
Edit History (please click the blue arrow to see the details)
