Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

CRC 901 – On-The-Fly Computing (OTF Computing) Show image information

CRC 901 – On-The-Fly Computing (OTF Computing)

Wednesday, 13.07.2016 | 14.00 Uhr | Fürstenallee 11, Raum F1.110

Talk given by Dr. Dennis Komm (ETH Zürich)

On July 13, 2016, Dr. Dennis Komm 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.

The University for the Information Society