Title: Online Optimization with Uncertain Information

Abstract:

In many real-life optimization problems the input becomes available to the algorithm over time. The algorithm has to make a sequence of decisions in an "online" fashion, with zero or imperfect information about the future input. I present a framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework, I present online algorithms for the problem of allocation of online advertisement space to budget-constrained advertisers. This is motivated by real-world situations where search engines have historical data that provide reasonably accurate estimates of the frequency of search queries except in certain highly unpredictable yet economically valuable spikes in the search pattern. This talk is based on a joint work with Mohammad Mahdian and Amin Saberi.

Hamid Zadeh is a post-doc at Microsoft Research, NE.