document: Bid optimization for broad match ad auctions Ad auctions in sponsored search support `` broad match '' that allows an advertiser to target a large number of queries while bidding only on a limited number . While giving more expressiveness to advertisers , this feature makes it challenging to optimize bids to maximize their returns : choosing to bid on a query as a broad match because it provides high profit results in one bidding for related queries which may yield low or even negative profits . We abstract and study the complexity of the { \ em bid optimization problem } which is to determine an advertiser 's bids on a subset of keywords ( possibly using broad match ) so that her profit is maximized . In the query language model when the advertiser is allowed to bid on all queries as broad match , we present a linear programming ( LP ) - based polynomial-time algorithm that gets the optimal profit . In the model in which an advertiser can only bid on keywords , ie. , a subset of keywords as an exact or broad match , we show that this problem is not approximable within any reasonable approximation factor unless P = NP . To deal with this hardness result , we present a constant-factor approximation when the optimal profit significantly exceeds the cost . This algorithm is based on rounding a natural LP formulation of the problem . Finally , we study a budgeted variant of the problem , and show that in the query language model , one can find two budget constrained ad campaigns in polynomial time that implement the optimal bidding strategy . Our results are the first to address bid optimization under the broad match feature which is common in ad auctions .
doc_bio_tags: B I O O O B I B I O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O B I O O O O O O O O O B I O