AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The independent set problem in graphs is a classic problem in algorithms. For many practically relevant graph classes, including interval, disk, or rectangle graphs, there exist good approximation algorithms. Much less is known about the natural online variant of the problem - most likely due to simple worst-case lower bounds of \Omega(n) that apply even to interval graphs. 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.

Martin Hoefer

--email hidden

passcode not visible

logged in users only