Algorithm for Stochastic Multiple-Choice Knapsack Problem and Application to Keywords Bidding
We model budget-constrained keyword bidding in sponsored search auctions as a stochastic multiple-choice knapsack problem (S-MCKP) and design an algorithm to solve S-MCKP and the corresponding bidding optimization problem. Our algorithm selects items online based on a threshold function which can be built/updated using historical data. Our algorithm achieved about 99％ performance compared to the offline optimum when applied to a real bidding dataset. With synthetic dataset and iid item-sets, its performance ratio against the offline optimum converges to one empirically with increasing number of periods.
Sponsored search auction keyword bidding multiple-choice knapsack problem stochastic optimization
Yunhong Zhou Victor Naroditskiy
HP Labs 1501 Page Mill Rd Palo Alto, CA 94304 Department of Computer Science Brown University Providence, RI 02912
国际会议
第十七届国际万维网大会(the 17th International World Wide Web Conference)(WWW08)
北京
英文
2008-04-21（万方平台首次上网日期，不代表论文的发表时间）