The Taub Faculty of Computer Science Events and Talks

Motivated by Internet targeted advertising, we address several ad allocation problems. While prior work has established that these problems admit no randomized online algorithm with competitive ratio better than $1-\frac{1}{e}~63.2%$ [KVV90,MSVV2005], simple heuristics have been observed to perform much better in practice than suggested by these bounds. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al. [BJN2007], graphs which we call $(k,d)-bounded$. In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$. We prove that for such graphs (and a generalization thereof for the AdWords problem), the natural greedy algorithms for these problems achieve a competitive ratio of $1-\frac{d-1}{k+d-1}$, tending to \emph{one} as $d/k$ tends to zero. We prove that the bound is tight for these algorithms.

Inspired by our tight examples for the performance of greedy algorithms, we develop deterministic primal-dual algorithms for the above problems which achieve competitive ratio of $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$, or \emph{exponentially} better loss as a function of $k/d$. This is strictly better than $1-\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms' dual updates to prove by dual-fitting that simple randomized algorithms, including \textsc{ranking} of Karp et al., achieve the same bounds in expectation as our deterministic algorithms. Our primal-dual algorithms and analysis differ from previous online primal dual-algorithms, both for this problem and in general. Our approach may prove useful in designing theoretically as well practically better algorithms for other "well-behaved" problems.

Joint work with Seffi Naor.