Adaptive Budget Allocation for Maximizing Influence of Advertisements
Adaptive Budget Allocation for Maximizing Influence of Advertisements
复制标题
DOI：
--
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Daisuke Hatano;Takuro Fukunaga;K. Kawarabayashi
中科院分区：
文献类型：
--
作者：
Daisuke Hatano;Takuro Fukunaga;K. Kawarabayashi
预算分配问题是广告策划中产生的优化问题。在这个问题中，广告商在媒体上分配的预算有限，并寻求优化分配，以便最大部分的客户能够受到影响。已知该问题采用 (1-1/e) 近似算法。然而，之前关于这个问题的研究没有考虑过根据过去活动的效果自适应地调整分配，这是现实环境中的常见策略。我们在本文中的主要贡献是分析预算分配问题的自适应策略。我们定义一个贪婪策略，称为不敏感策略，然后给出可证明的性能保证。这一结果是通过将自适应子模性（在主动学习和随机优化背景下研究的概念）扩展到整数格上的函数而获得的。
The budget allocation problem is an optimization problem arising from advertising planning. In the problem, an advertiser has limited budgets to allocate across media, and seeks to optimize the allocation such that the largest fraction of customers can be influenced. It is known that this problem admits a (1-1/e)-approximation algorithm. However, no previous studies on this problem considered adjusting the allocation adaptively based upon the effect of the past campaigns, which is a usual strategy in the real setting. Our main contribution in this paper is to analyze adaptive strategies for the budget allocation problem. We define a greedy strategy, referred to as the insensitive policy, and then give a provable performance guarantee. This result is obtained by extending the adaptive submodularity, which is a concept studied in the context of active learning and stochastic optimization, to the functions over an integer lattice.