Using Predicted Weights for Ad Delivery
Using Predicted Weights for Ad Delivery
复制标题
使用预测权重进行广告投放
DOI：
10.1137/1.9781611976830.3
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xu, C.
中科院分区：
文献类型：
--
作者：
Lavastida, T.;Ravi R.;Moseley, B.;Xu, C.
我们研究了一种用于在线有能力二部匹配建模印象广告投放的比例权重算法的性能。该算法使用对广告商节点的预测，以与其邻居的权重成比例地匹配到达的印象节点。本文对该算法在雅虎广告印象数据集上的性能进行了深入的实证研究。并展示了其与自然基线（如贪心注水算法和排序算法）相比的优越性能。比例权重算法最近在理论文献中引起了人们的兴趣，在理论文献中，它被证明具有比增强了预测的最坏情况算法模型更强的保证。我们将这些结果扩展到广告商的能力不再随着时间的推移而固定的情况。此外，我们表明，当印象数量和最优匹配足够大时，该算法在随机顺序到达模型中具有接近最优的性能。
We study the performance of a proportional weights algorithm for online capacitated bipartite matching modeling the delivery of impression ads. The algorithm uses predictions on the advertiser nodes to match arriving impression nodes fractionally in proportion to the weights of its neighbors. This paper gives a thorough empirical study of the performance of the algorithm on a data-set of ad impressions from Yahoo! and shows its superior performance compared to natural baselines such as a greedy water-filling algorithm and the ranking algorithm.The proportional weights algorithm has recently received interest in the theoretical literature where it was shown to have strong guarantees beyond the worst-case model of algorithms augmented with predictions. We extend these results to the case where the advertisers’ capacities are no longer stationary over time. Additionally, we show the algorithm has near optimal performance in the random-order arrival model when the number of impressions and the optimal matching are sufficiently large.
登录
查看更多内容
DOI：
10.4230/lipics.esa.2021.59
发表时间：
2020-11
期刊：
ArXiv
影响因子：
--
作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
通讯作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
DOI：
10.1007/978-3-642-31594-7_59
发表时间：
2012-04
期刊：
--
影响因子：
--
作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
通讯作者：
Marco Molinaro Carnegie;Mellon R. Ravi;C. Mellon
DOI：
--
发表时间：
2019
期刊：
not applicable - unpublished manuscript
影响因子：
--
作者：
Balcan, M.F.;DeBlasio, D.;Dick, T.;Kingsford, C.;Sandholm, T.;Vitercik, E.
通讯作者：
Vitercik, E.
影响因子：
2.7
作者：
Agrawal, Shipra;Wang, Zizhuo;Ye, Yinyu
通讯作者：
Ye, Yinyu
DOI：
10.1016/j.disopt.2023.100778
发表时间：
2020-06
期刊：
ArXiv
影响因子：
--
作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev
通讯作者：
A. Antoniadis;Themis Gouleakis;P. Kleer;Pavel Kolev