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.)