| Mittagsseminar Talk Information | |
Date and Time: Thursday, January 22, 2009, 12:15 pm Duration: This information is not available in the database Location: CAB G51 Speaker: Panagiotis Cheilaris (City Univ. of New York and Rényi Institute) Online conflict-free coloring for geometric hypergraphs
A conflict-free coloring of a hypergraph H=(V,E) is a coloring of V
such that for any hyperedge e in E there exists a vertex v in e
with a uniquely occurring color in e. Conflict-free coloring of
hypergraphs induced by geometric shapes, like intervals on the
line, or disks on the plane, has applications in frequency
assignment in cellular networks. Colors model frequencies and
since the frequency spectrum is limited and expensive, the goal of
an algorithm is to minimize the number of assigned frequencies,
that is, reuse frequencies as much as possible.
We concentrate on an online variation of the problem. For
deterministic algorithms, we introduce a hierarchy of models
ranging from static to online and we compute lower and upper
bounds on the numbers of colors used, giving among other things
the first algorithm using a logarithmic number of colors in a
non-trivial online model. In the randomized oblivious adversary
model, we introduce a framework for conflict-free coloring a
specific class of hypergraphs with a logarithmic number of colors.
This specific class includes many hypergraphs arising in geometry
and gives an online randomized algorithm that uses less colors and
less random bits than other algorithms in the literature. Based on
the same framework, we initiate the study of online deterministic
algorithms that recolor few points.
Some of the above results are joint work with Amotz Bar-Noy,
Svetlana Olonetsky, and Shakhar Smorodinsky.
Upcoming talks | All previous talks | Talks by speaker |  Upcoming talks in iCal format (beta version!) Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login
|
