Online Ad Assignment with Free Disposal

We study an online weighted assignment problem with a set of fixed nodes corresponding to advertisers and online arrival of nodes corresponding to ad impressions. Advertiser

a

has a contract for

n

(

a

) impressions, and each impression has a set of weighted edges to advertisers. The problem is to assign the impressions online so that while each advertiser

a

gets

n

(

a

) impressions, the total weight of edges assigned is maximized.

Our insight is that ad impressions allow for

free disposal

, that is, advertisers are indifferent to, or prefer being assigned more than

n

(

a

) impressions without changing the contract terms. This means that the value of an assignment

only

includes the

n

(

a

) highest-weighted items assigned to each node

a

. With free disposal, we provide an algorithm for this problem that achieves a competitive ratio of 1 − 1/

e

against the offline optimum, and show that this is the best possible ratio. We use a primal/dual framework to derive our results, applying a novel exponentially-weighted dual update rule. Furthermore, our algorithm can be applied to a general set of assignment problems including the

ad words

problem as a special case, matching the previously known 1 − 1/

e

competitive ratio.