Abstract
Internet advertising revenue has surpassed broadcast revenue (including cable televisions) very recently due to the rapid growth of e-commerce and
information technology. As online advertising has
become a major source of revenue for online publishers, such as Google and Amazon, one problem
facing them is to optimize the ads selection and allocation in order to maximize their revenue. Although there is a rich body of work that has been
devoted to this field, uncertainty about models and
parameter settings is largely ignored in existing algorithm design. To fill this gap, we are the first to
formulate and study the Robust Ad Allocation problem, by taking into account the uncertainty about
parameter settings. We define a Robust Ad Allocation framework with a set of candidate parameter settings, typically derived from different users
or topics. Our main aim is to develop robust ad
allocation algorithms, which can provide satisfactory performance across a spectrum of parameter
settings, compared to the (parameter-specific) optimum solutions. We study this problem progressively and propose a series of algorithms with bounded
approximation ratio