Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Ajwani, Deepak Elbassioni, Khaled M. Govindarajan, Sathish Ray, Saurabh dblp dblp dblp dblp Not MPG Author(s): Ray, Saurabh
 Editor(s): Not MPII Editor(s): Scheideler, Christian
 BibTeX cite key*: Elbassioni2007a

 Title, Booktitle
 Title*: Conflict-Free Coloring for Rectangle Ranges Using $\tildeO(n^.382+\epsilon)$ Colors Booktitle*: 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 07)

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: San Diego, CA, USA Language: English Event Date* (no longer used): Organization: Event Start Date: 9 June 2007 Event End Date: 11 June 2007

 Publisher
 Name*: ACM URL: Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series: Proceedings
 Volume: Number: Month: June Pages: (to-appear) Year*: 2007 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 Note: To Appear (LaTeX) Abstract: Given a set of points $P\subseteq \RR^2$, a \emph{conflict-free coloring} of $P$ is an assignment of colors to points of $P$, such that each non-empty axis-parallel rectangle $T$ in the plane contains a point whose color is distinct from all other points in $P\cap T$. This notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of $n$ points in $\RR^2$ can be conflict-free colored with $\tO(n^{.382+\epsilon})$ colors in expected polynomial time, for any arbitrarily small $\eps > 0$. This improves upon the previously known bound of $O(\sqrt{n\log\log n/\log n}$). Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: popular Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Elbassioni2007a,
AUTHOR = {Ajwani, Deepak and Elbassioni, Khaled M. and Govindarajan, Sathish and Ray, Saurabh},
TITLE = {Conflict-Free Coloring for Rectangle Ranges Using $\tilde{O}(n^{.382+\epsilon})$ Colors},
BOOKTITLE = {19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 07)},
PUBLISHER = {ACM},
YEAR = {2007},
PAGES = {(to--appear)},
SERIES = {Proceedings},
ADDRESS = {San Diego, CA, USA},
MONTH = {June},
NOTE = {To Appear},
}