ARC Colloquium - Evangelia Gergatsouli

views comments

Talk title: Searching with Costly Information: When to Open Pandora’s Box

Abstract: In many optimization settings involving uncertainty in the input, we can obtain more accurate information on the input variables by paying at extra monetary or computational overhead. Determining the optimal manner for acquiring information then becomes an online decision-making problem: each piece of information obtained by the algorithm can affect whether and which piece to acquire next. Pandora's Box problem -an old economics paradigm- and its variants capture exactly settings like these, but require independence on the input variables - a somewhat unrealistic assumption. In this talk I will present our work on the correlated Pandora's box problem; the first approximation algorithms for the general setting where the input variables can be arbitrarily correlated. I will also discuss how this problem is tightly connected to well known problems in approximation/online algorithms and online learning.

Tags

ARC Colloquium - Evangelia Gergatsouli

Related Media