document: Budget constrained bidding in keyword auctions and online knapsack problems We consider the budget-constrained bidding optimization problem for sponsored search auctions , and model it as an online ( multiple-choice ) knapsack problem . We design both deterministic and randomized algorithms for the online ( multiple-choice ) knapsack problems achieving a provably optimal competitive ratio . This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser . Our bidding strategy for revenue maximization is oblivious ( i.e. , without knowledge ) of other bidders ' prices and\/or click-through-rates for those positions . We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually , and also discuss a sniping heuristic that strictly improves bidding performance . With sniping and parameter tuning enabled , our bidding algorithms can achieve a performance ratio above 90 % against the optimum by the omniscient bidder .
doc_bio_tags: 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