Begin: Wed, 13. of Jul 2016 ( 2:00 PM)
Location: Fürstenallee 11, Raum F1.110
On July 13, 2016, Dr. Dennis Komm (ETH Zürich) will give a talk about "Information Content of Online Problems" in the context of the SFB 901.
Abstract:
In online computation, the input of a computational problem is revealed gradually such that parts of the definite output need to be given with incomplete information. Using competitive analysis, one usually studies the resulting loss in solution quality. In this talk, another aspect is investigated, namely how a potentially critical part of the input can be both identified and quantified. Therefore, we study so called online algorithms with advice, i.e., online algorithms that obtain additional information about the input at hand, which allows them to increase their solution quality. Our goal is to give bounds on the information both necessary and sufficient in order to obtain a given competitive ratio. Our results have also impact on randomized online computation.
