## March 4, 2016:

#
Probabilistic Mutually Exclusive Task Sequencing, with Applications to
Online Advertising

##
Dmitri Arkhipov

One by one solicitation (OBOS) is one of two dominant strategies for
filling ad space in Web content on-demand. In OBOS an ad network
sequentially solicits applicable in-network advertisers in some
order. Each ad space should fill in no more than 200ms, but both whether
a solicitation is successful, and the magnitude of the round trip
network delay of the solicitation are random variables. We study the
problem of determining an optimal order of solicitation.

We present a dynamic programming (DP) formulation of the problem
solvable in time exponential in the number of applicable
advertisers. For larger instances we describe an approximate DP (ADP)
formulation based on the real time dynamic programming (RTDP)
technique. We compare both the DP and ADP to a greedy randomized
adaptive search procedure (GRASP) local search.

Our ADP formulation requires as a subroutine a tractable algorithm
for calculating an upper bound value for our problem. We present a
relaxation of our original problem; the solution of our relaxed problem
is an upper bound for our original problem. We present a
pseudo-polynomial time solution algorithm for our relaxed problem.

(Joint work with John Turner, Michael Dillencourt, and Amelia Regan.)