• Calendar

May 26, Monday
12:00 – 14:00

A conflict-free coloring (CF-coloring) of 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 unique color in e (i.e., no other vertex of e has the same color as v). The problem was introduced by Even et al. In 2002 and has applications in frequency assignment for cellular networks. We will briefly review the literature. We investigate deterministic online algorithms for the above problem for hypergraphs that arise in geometry (conflict-free coloring collinear points with respect to intervals). The best offline algorithm uses $O(\log n)$ colors, whereas the best online algorithm from Chen et al. uses $O(log^2 n)$ colors. We give the first deterministic online algorithm using $O(\log n)$ colors, in a non-trivial online model. We also provide a tight analysis of the worst-case performance of the greedy algorithm, solving an open problem from Chen et al.

We provide a framework for online CF-coloring any hypergraph in the oblivious adversary model. We use this framework to obtain efficient (order-optimal, i.e. using logarithmic number of colors) randomized online algorithms for CF-coloring some hypergraphs that arise in geometry and model an important version of the frequency assignment task for cellular networks. Our algorithms use fewer random bits and fewer colors than other algorithms in the literature. We also initiate the study of deterministic online CF-coloring with recoloring. The goal is to use few colors, but also resort to recoloring as little as possible. We provide algorithms using $O(\log n)$ colors and doing $O(n)$ recolorings.

Joint work with Amotz Bar-Noy, Svetlana Olonetsky, and Shakhar Smorodinsky