2025-11-23T02:01:16.750653

Multi-product Influence Maximization in Billboard Advertisement

Ali, Islam, Banerjee

Billboard Advertisement has emerged as an effective out-of-home advertisement technique where the goal is to select a limited number of slots and play advertisement content over there with the hope that this will be observed by many people, and effectively, a significant number of them will be influenced towards the brand. Given a trajectory and a billboard database and a positive integer $k$, how can we select $k$ highly influential slots to maximize influence? In this paper, we study a variant of this problem where a commercial house wants to make a promotion of multiple products, and there is an influence demand for each product. We have studied two variants of the problem. In the first variant, our goal is to select $k$ slots such that the respective influence demand of each product is satisfied. In the other variant of the problem, we are given with $\ell$ integers $k_1,k_2, \ldots, k_{\ell}$, the goal here is to search for $\ell$ many set of slots $S_1, S_2, \ldots, S_{\ell}$ such that for all $i \in [\ell]$, $|S_{i}| \leq k_i$ and for all $i \neq j$, $S_i \cap S_j=\emptyset$ and the influence demand of each of the products gets satisfied. We model the first variant of the problem as a multi-submodular cover problem and the second variant as its generalization. For solving the first variant, we adopt the bi-criteria approximation algorithm, and for the other variant, we propose a sampling-based approximation algorithm. Extensive experiments with real-world trajectory and billboard datasets highlight the effectiveness and efficiency of the proposed solution approach.

academic

Multi-product Influence Maximization in Billboard Advertisement

基本信息

论文ID: 2510.09050
标题: Multi-product Influence Maximization in Billboard Advertisement
作者: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
分类: cs.DS (Data Structures and Algorithms), cs.DB (Databases)
发表时间: 2025年10月10日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.09050

户外广告的重要性: 商业公司通常将总收入的7-10%用于广告，户外广告牌因其投资回报保证和易用性成为有效方法
传统问题的局限性: 现有研究主要关注单一广告商的影响力最大化或多广告商间的遗憾最小化
实际需求: 商业公司通常需要同时推广多种异构产品，每种产品针对不同的客户群体

研究动机

实践需求: 现实中广告商需要在统一预算内满足多种产品的不同影响力需求
理论空白: 现有文献缺乏针对多产品广告牌时段选择问题的研究
技术挑战: 需要在满足各产品影响力约束的同时最小化总成本

核心贡献

问题扩展: 将影响力时段选择问题扩展到多产品广告场景，研究了两个相关的问题变体
理论建模: 将第一个变体建模为多子模覆盖问题，第二个变体建模为其泛化版本
算法设计:
- 为第一个变体采用双准则近似算法
- 为第二个变体提出基于采样的近似算法
效率优化: 开发了高效的启发式解决方案以解决可扩展性问题
实验验证: 在真实轨迹和广告牌数据集上进行了广泛实验

方法详解

任务定义

输入:

轨迹数据库D: 包含用户位置-时间信息和产品兴趣
广告牌数据库B: 包含广告牌位置、时段和成本信息
成本函数c: BS → R⁺
产品集合P = {1,2,...,ℓ}

两个问题变体:

Common Multi-Product Slot Selection Problem:
- 选择单一时段集合S ⊆ BS
- 最小化总成本∑_{s∈S} c(s)
- 满足约束: ∀j ∈ ℓ, I_j(S) ≥ k_j
Disjoint Multi-Product Slot Selection Problem:
- 选择ℓ个互不相交的时段集合S₁,S₂,...,S_ℓ
- 满足: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

核心技术

1. 影响力函数建模

产品j的影响力函数定义为:

I_j(S) = ∑_{u_i∈U_j} [1 - ∏_{s_j∈S} (1 - Pr(s_j, u_i))]

其中U_j是对产品j感兴趣的用户集合，Pr(s_j, u_i)是时段s_j对用户u_i的影响概率。

2. 子模性质

影响力函数具有子模性质，满足边际递减效应：

f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B), ∀A ⊆ B

算法架构

Algorithm 1: Common Slot Selection的双准则近似算法

标准化: 将每个产品的影响力函数标准化，使I_j(BS) = 1
连续贪心: 使用多线性扩展在拟阵多面体上求解分数解
随机舍入: 采样ℓ = ⌈log_{1/(1-ε)}(r)⌉个随机子集
修复步骤: 对未满足约束的产品贪心添加时段

Algorithm 2: Disjoint Slot Selection的采样算法

排列采样: 随机采样产品-时段分配的排列
贪心分配: 按排列顺序为每个产品贪心选择时段
可行性检查: 验证是否满足所有约束
最优选择: 返回成本最小的可行解

技术创新点

多线性扩展应用: 将子模函数的连续扩展技术应用于多产品场景
采样复杂度分析: 使用Hoeffding不等式分析采样算法的样本复杂度
双准则近似: 在满足影响力约束的同时提供成本近似保证

实验设置

数据集

New York City (NYC):
- 227,428个签到记录 (2012年4月-2013年2月)
- 1,083个独特用户
- 716个广告牌，1,031,040个时段
Los Angeles (LA):
- 74,170个签到记录，覆盖15条街道
- 2,000个独特用户
- 1,483个广告牌，2,135,520个时段