  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_i\cdot \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(k\cdot n^{2k + 1})$ time.
