Title: Price of information in combinatorial optimization
| Speaker: | David Aleman Espinosa |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Pandora's box is a classical example of a combinatorial optimization problem in which the input is uncertain and can only be revealed to us after paying probing prices.
In this problem we are given a set of n items, where each i ∈ [n] has a deterministic probing price pi ∈ R+ and a random cost Ci ∈ R+. The cost Ci is only revealed after the probing price pi is paid. The goal is to adaptively probe a subset of items S ⊆ [n] and select a probed item in order to minimize the expected selection cost plus probing price: E[min_{i∈S} Ci + ∑_{i∈S} pi]. It is well known that if the costs are independent then the problem admits an efficient and simple optimal policy.
In this talk we discuss a paper by Sahil Singla that studies a generalization of this model to more general combinatorial optimization problems such as matching, set cover and facility location.