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:








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, Abstract, ©

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},
}


Entry last modified by Deepak Ajwani, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni
Created
03/01/2007 04:35:35 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Deepak Ajwani
Deepak Ajwani
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
05/06/2007 02:49:08 PM
05/06/2007 02:48:29 PM
02.05.2007 15:28:53
03/02/2007 06:37:58 PM
03/02/2007 05:32:14 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section