Prof. Emo Welzl and Prof. Bernd Gärtner
|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)
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.
Automatic MiSe System Software Version 1.4803M | admin login