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 θ to slot j is vi⋅αθj where vi is an advertiser-specific value and each ad type θ has a discount curve α(θ)1≥α(θ)2≥…≥0 over the slots that is common for ads of type θ. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in O(n2(k+logn)) time for n slots and n ads of each type—cf. O(kn3) when using the Hungarian algorithm—, and 2) we show to do VCG pricing in asymptotically the same time, namely O(n2(k+logn)), and apply reserve prices in O(n3(k+logn)). The Ad Types Problem (with gap rules) includes a matrix G such that after we show an ad of type θi, the next Gij slots cannot show an ad of type θj. We show that the problem is hard to approximate within k1−ϵ for any ϵ>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⋅n2k+1) time.