Summary: We study the following online problem. Each advertiser \(a_{i}\) has a value \(v_{i}\), demand \(d_{i}\), and frequency cap \(f_{i}\). Supply units arrive online, each one associated with a user. Each advertiser can be assigned at most \(d_{i}\) units in all, and at most \(f_{i}\) units from the same user. The goal is to design an online allocation algorithm maximizing total value.
We first show a deterministic upper bound of 3/4-competitiveness, even when all frequency caps are 1, and all advertisers share identical values and demands. A competitive ratio approaching \(1 - 1/e\) can be achieved via a reduction to a model with arbitrary decreasing valuations [G. Goel and A. Mehta, Lect. Notes Comput. Sci. 4858, 335–340 (2007; Zbl 1306.90070)]. Our main contribution is analyzing two 3/4-competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal demands. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the \(1 - 1/e\) ratio.
For the entire collection see [Zbl 1219.68015].