Scholarlink

<p>In a typical <i>billboard advertisement</i> technique, a number of digital billboards are owned by an <i>influence provider</i>, and many advertisers approach the influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider provides the demanded or more influence, then he will receive the full payment, or else a partial payment. In the context of an influence provider, if he provides more or less than the advertiser demands, it is a loss for him. This is formalized as ‘Regret,’ and naturally, in the context of the influence provider, the goal will be to allocate the billboard slots among the advertisers such that the total regret is minimized. In this paper, we study this problem as a discrete optimization problem and propose four solution approaches. The first method selects the billboard slots from the available ones in an incremental, greedy manner, and we refer to this approach as the budget-effective greedy method. In the second one, we introduce randomness with the first one, where we perform the marginal gain computation for a sample of randomly chosen billboard slots. The remaining two approaches are further improvements over the second one. We analyze all the algorithms to understand their time and space complexity. We implement them with real-life trajectory and billboard datasets and conduct a number of experiments. It has been observed that the randomized budget-effective greedy approach takes reasonable computational time while minimizing the regret.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Minimizing regret in billboard advertisement under zonal influence constraint

  • 期刊论文

  • 发表日期：

    2026年4月30日

查看全文
  • Dildar Ali,
  • Suman Banerjee,
  • Yamuna Prasad

摘要

In a typical billboard advertisement technique, a number of digital billboards are owned by an influence provider, and many advertisers approach the influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider provides the demanded or more influence, then he will receive the full payment, or else a partial payment. In the context of an influence provider, if he provides more or less than the advertiser demands, it is a loss for him. This is formalized as ‘Regret,’ and naturally, in the context of the influence provider, the goal will be to allocate the billboard slots among the advertisers such that the total regret is minimized. In this paper, we study this problem as a discrete optimization problem and propose four solution approaches. The first method selects the billboard slots from the available ones in an incremental, greedy manner, and we refer to this approach as the budget-effective greedy method. In the second one, we introduce randomness with the first one, where we perform the marginal gain computation for a sample of randomly chosen billboard slots. The remaining two approaches are further improvements over the second one. We analyze all the algorithms to understand their time and space complexity. We implement them with real-life trajectory and billboard datasets and conduct a number of experiments. It has been observed that the randomized budget-effective greedy approach takes reasonable computational time while minimizing the regret.