Online Learning of Assignments that Maximize Submodular Functions
  Which ads should we display in sponsored search in order to maximize our
revenue? How should we dynamically rank information sources to maximize value
of information? These applications exhibit strong diminishing returns:
Selection of redundant ads and information sources decreases their marginal
utility. We show that these and other problems can be formalized as repeatedly
selecting an assignment of items to positions to maximize a sequence of
monotone submodular functions that arrive one by one. We present an efficient
algorithm for this general problem and analyze it in the no-regret model. Our
algorithm possesses strong theoretical guarantees, such as a performance ratio
that converges to the optimal constant of 1-1/e. We empirically evaluate our
algorithm on two real-world online optimization problems on the web: ad
allocation with submodular utilities, and dynamically ranking blogs to detect
information cascades.
