The Ad Types Problem

The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $theta$ to slot $j$ is $v_icdot alpha^{theta}_j$ where $v_i$ is an advertiser-specific value and each ad type $theta$ has a discount curve $alpha^{(theta)}_{1} ge alpha^{(theta)}_{2} ge ... ge 0$ over the slots that is common for ads of type $theta$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + log n))$, and apply reserve prices in $O(n^3(k + log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $theta_i$, the next $G_{ij}$ slots cannot show an ad of type $theta_j$. We show that the problem is hard to approximate within $k^{1- epsilon}$ for any $epsilon > 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(kcdot n^{2k + 1})$ time.