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

看板広告における多製品影響力最大化

基本情報

論文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 (データ構造とアルゴリズム)、cs.DB (データベース)
発表日: 2025年10月10日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.09050

要約

屋外看板広告は、限定された時間枠を選択してその中に広告コンテンツを放映し、多くの人々に観察され、ブランドに対する態度に効果的に影響を与えることを目標とする効果的な屋外広告技術となっています。本論文は変種問題を研究しています。商業企業は複数の製品を推進したいと考えており、各製品には影響力要件があります。2つの問題変種を研究しました。第1の変種の目標は、k個の時間枠を選択して、各製品の対応する影響力要件を満たすことです。第2の変種では、ℓ個の整数k₁,k₂,...,k_ℓが与えられ、目標はℓ個の時間枠集合S₁,S₂,...,S_ℓを見つけることであり、相互に素であり、各製品の影響力要件を満たします。

研究背景と動機

問題背景

屋外広告の重要性: 商業企業は通常、総収入の7～10%を広告に費やしており、屋外看板は投資収益率の保証と使いやすさのため効果的な方法となっています
従来の問題の限界: 既存の研究は主に単一広告主の影響力最大化または複数広告主間の後悔最小化に焦点を当てています
実際のニーズ: 商業企業は通常、異なる顧客グループを対象とした複数の異種製品を同時に推進する必要があります

研究の動機

実践的ニーズ: 現実では広告主は統一予算内で複数製品の異なる影響力要件を満たす必要があります
理論的空白: 既存文献は多製品看板時間枠選択問題に関する研究が不足しています
技術的課題: 各製品の影響力制約を満たしながら総コストを最小化する必要があります

核心的貢献

問題の拡張: 影響力時間枠選択問題を多製品広告シナリオに拡張し、2つの関連する問題変種を研究しました
理論的モデリング: 第1の変種を多部分モジュラー被覆問題としてモデル化し、第2の変種をその一般化版としてモデル化しました
アルゴリズム設計:
- 第1の変種に対して双基準近似アルゴリズムを採用
- 第2の変種に対してサンプリングベースの近似アルゴリズムを提案
効率最適化: スケーラビリティ問題を解決するための効率的なヒューリスティック解を開発しました
実験検証: 実軌跡と看板データセット上で広範な実験を実施しました

方法の詳細

タスク定義

入力:

軌跡データベースD: ユーザー位置-時間情報と製品興味を含む
看板データベースB: 看板位置、時間枠、コスト情報を含む
コスト関数c: BS → R⁺
製品集合P = {1,2,...,ℓ}

2つの問題変種:

共通多製品時間枠選択問題:
- 単一時間枠集合S ⊆ BSを選択
- 総コスト∑_{s∈S} c(s)を最小化
- 制約を満たす: ∀j ∈ ℓ, I_j(S) ≥ k_j
素な多製品時間枠選択問題:
- ℓ個の相互に素な時間枠集合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

アルゴリズムアーキテクチャ

アルゴリズム1: 共通時間枠選択の双基準近似アルゴリズム

正規化: 各製品の影響力関数を正規化し、I_j(BS) = 1とします
連続貪欲: マトロイド多面体上の多線形拡張を使用して分数解を求解
ランダム丸め: ℓ = ⌈log_{1/(1-ε)}(r)⌉個のランダム部分集合をサンプリング
修復ステップ: 制約を満たさない製品に対して貪欲に時間枠を追加

アルゴリズム2: 素な時間枠選択のサンプリングアルゴリズム

順列サンプリング: 製品-時間枠割り当ての順列をランダムサンプリング
貪欲割り当て: 順列順に各製品に対して貪欲に時間枠を選択
実行可能性チェック: すべての制約を満たすかどうかを検証
最適選択: コスト最小の実行可能解を返す

技術的革新点

多線形拡張の応用: 部分モジュラー関数の連続拡張技術を多製品シナリオに適用
サンプリング複雑性分析: Hoeffding不等式を使用してサンプリングアルゴリズムのサンプル複雑性を分析
双基準近似: 影響力制約を満たしながらコスト近似保証を提供

実験設定

データセット

ニューヨーク市 (NYC):
- 227,428チェックイン記録 (2012年4月～2013年2月)
- 1,083人のユニークユーザー
- 716個の看板、1,031,040個の時間枠
ロサンゼルス (LA):
- 74,170チェックイン記録、15条の街路をカバー
- 2,000人のユニークユーザー
- 1,483個の看板、2,135,520個の時間枠