Optimization and Approximation under Partial Information
Sudipto Guha, UPenn
October 26, 2007, 3:30PM, Wean 7220
Abstract:
If you had to bet on a race — and you have ten minutes before the race begins, which contestants would you chat to for information? Would you decide on the sequence of contestants you would talk to upfront or choose adaptively? Coincidentally, this same problem and its variants appear in several applications such as databases, planning, and sensor networks, where parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system, as captured by some objective function over the parameters, is significantly improved if some of these parameters can be probed or observed. In a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. This problem and its variants are the focus of this talk where we will consider them through the lens of approximation algorithms.
