–
January 5, 2016
The independent set problem in graphs is a classic and well-studied combinatorial optimization problem with many applications. Recently, generalized variants have become prominent in the study of algorithms for realistic interference models in wireless networks. Perhaps surprisingly, much less is known about the natural online variant of the problem where nodes and edges of the graph arrive sequentially over time. In this talk I highlight some of our recent work for online variants with stochastic adversaries, including O(1)-competitive algorithms for interval and disk graphs. These results can be extended to polylogarithmic guarantees for rectangle graphs and for more general online admission problems in wireless networks.
