Campus Event Calendar

Event Entry

What and Who

Online Independent Set with Stochastic Adversaries

Martin Hoefer
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Tuesday, 18 February 2014
30 Minutes
E1 4


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

Martin Hoefer, 01/21/2014 20:19 -- Created document.