Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, January 22, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

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:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  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.4803M   |   admin login