Multi-product Influence Maximization in Billboard Advertisement

Basic Information

• Paper ID: 2510.09050
• Title: Multi-product Influence Maximization in Billboard Advertisement
• Authors: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
• Classification: cs.DS (Data Structures and Algorithms), cs.DB (Databases)
• Publication Date: October 10, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.09050

Abstract

Billboard advertisements have become an effective outdoor advertising technology, aiming to select a limited number of time slots for displaying advertisements with the goal of maximizing visibility and effectively influencing public attitudes toward brands. This paper investigates a variant problem: commercial companies wish to promote multiple products, each with specific influence requirements. Two problem variants are studied: the first variant aims to select k time slots such that the corresponding influence requirements for each product are satisfied; the second variant, given ℓ integers k₁, k₂, ..., k_ℓ, seeks to find ℓ disjoint time slot sets S₁, S₂, ..., S_ℓ that satisfy mutual disjointness while meeting the influence requirements for each product.

Research Background and Motivation

Problem Context

1. Importance of Outdoor Advertising: Commercial companies typically allocate 7-10% of total revenue to advertising, with billboards being an effective method due to guaranteed return on investment and ease of use
2. Limitations of Traditional Approaches: Existing research primarily focuses on influence maximization for single advertisers or regret minimization among multiple advertisers
3. Practical Requirements: Commercial companies typically need to simultaneously promote multiple heterogeneous products, each targeting different customer segments

Research Motivation

• Practical Needs: Advertisers in reality need to satisfy different influence requirements for multiple products within a unified budget
• Theoretical Gap: Existing literature lacks systematic research on multi-product billboard time slot selection problems
• Technical Challenges: Need to minimize total cost while satisfying influence constraints for all products

Core Contributions

1. Problem Extension: Extends the influence time slot selection problem to multi-product billboard scenarios, investigating two related problem variants
2. Theoretical Modeling: Models the first variant as a multi-submodular coverage problem and the second variant as its generalization
3. Algorithm Design:
   • Adopts bicriteria approximation algorithm for the first variant
   • Proposes sampling-based approximation algorithm for the second variant
4. Efficiency Optimization: Develops efficient heuristic solutions to address scalability issues
5. Experimental Validation: Conducts extensive experiments on real trajectory and billboard datasets

Methodology Details

Task Definition

Input:

• Trajectory database D: Contains user location-time information and product interests
• Billboard database B: Contains billboard locations, time slots, and cost information
• Cost function c: BS → R⁺
• Product set P = {1, 2, ..., ℓ}

Two Problem Variants:

1. Common Multi-Product Slot Selection Problem:
   • Select a single time slot set S ⊆ BS
   • Minimize total cost ∑_{s∈S} c(s)
   • Satisfy constraints: ∀j ∈ ℓ, I_j(S) ≥ k_j
2. Disjoint Multi-Product Slot Selection Problem:
   • Select ℓ mutually disjoint time slot sets S₁, S₂, ..., S_ℓ
   • Satisfy: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

Core Techniques

1. Influence Function Modeling

The influence function for product j is defined as:

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

where U_j is the set of users interested in product j, and Pr(s_j, u_i) is the influence probability of time slot s_j on user u_i.

2. Submodularity Property

The influence function exhibits submodularity, satisfying the diminishing marginal returns property:

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

Algorithm Architecture

Algorithm 1: Bicriteria Approximation Algorithm for Common Slot Selection

1. Normalization: Normalizes each product's influence function such that I_j(BS) = 1
2. Continuous Greedy: Uses multilinear relaxation to solve fractional solutions on the matroid polytope
3. Randomized Rounding: Samples ℓ = ⌈log_{1/(1-ε)}(r)⌉ random subsets
4. Repair Step: Greedily adds time slots for products with unsatisfied constraints

Algorithm 2: Sampling Algorithm for Disjoint Slot Selection

1. Permutation Sampling: Randomly samples permutations of product-slot assignments
2. Greedy Allocation: Greedily selects time slots for each product in permutation order
3. Feasibility Check: Verifies satisfaction of all constraints
4. Optimal Selection: Returns the minimum-cost feasible solution

Technical Innovations

1. Multilinear Relaxation Application: Applies continuous extension techniques for submodular functions to multi-product scenarios
2. Sampling Complexity Analysis: Uses Hoeffding's inequality to analyze sample complexity of the sampling algorithm
3. Bicriteria Approximation: Provides cost approximation guarantees while satisfying influence constraints

Experimental Setup

Datasets

1. New York City (NYC):
   • 227,428 check-in records (April 2012 - February 2013)
   • 1,083 unique users
   • 716 billboards, 1,031,040 time slots
2. Los Angeles (LA):
   • 74,170 check-in records covering 15 streets
   • 2,000 unique users
   • 1,483 billboards, 2,135,520 time slots

Evaluation Metrics

• Influence: Total influence achieved for each product
• Slot Count: Total number of slots allocated to each product
• Computation Time: Algorithm execution time
• Cost: Total cost of time slot selection

Baseline Methods

1. Random Allocation (RA): Randomly selects time slots for product allocation
2. Top-k Allocation: Prioritizes high-influence slots based on influence value ranking

Key Parameters

• Demand-Supply Ratio α: Ratio of global influence demand to total supply (40%-120%)
• Individual Demand Ratio β: Ratio of average individual demand to total supply (1%-20%)
• Number of Products |P|: 5, 10, 20, 50, 100
• Distance Parameter λ: 25m-150m
• Approximation Parameter ε: 0.01-0.2

Experimental Results

Main Findings

Influence Performance

• NYC Dataset: BCA method outperforms baseline methods by 20-25%, with RA method showing best performance
• LA Dataset: BCA method outperforms baseline methods by 8-10%
• When α ≥ 100% and β ≥ 10%, demand exceeds supply; BCA method outperforms baseline while RA method has no feasible solution

Slot Allocation Efficiency

• As α and β increase, the number of slots allocated to each product increases
• Top-k method allocates fewer slots than Random method
• BCA method allocates more slots than RA and baseline methods (to satisfy all product requirements)

Computational Complexity

• Time Complexity:
  • BCA algorithm: O(n²ℓ/ε + nℓ)
  • RA algorithm: O(|X|·ℓ·B_max/c_min·n·t)
• RA method has longest computation time (requires considering numerous permutations)
• BCA method has moderate time, growing slowly with α and β

Cost Efficiency

• RA method achieves optimal cost performance, using minimum cost to satisfy all product requirements
• As demand increases, allocation costs for all methods rise

Theoretical Guarantees

Approximation Ratio of BCA Algorithm

Theorem: Let r be the sparsity (maximum number of functions any single slot can contribute to), ε > 0. The BCA algorithm returns with high probability a set S satisfying:

• For all j ∈ ℓ: I_j(S) ≥ (1 - 1/e - ε)·k_j
• Expected cost: Ec(S) = O(1/ε·log r)·OPT

Sampling Complexity

Theorem: For any ε, δ ∈ (0,1), if sample size ≥ ln(2/δ)·c(BS)²/(2ε²·(W_A)²), then the probability that computational error is less than ε is at least (1-δ).

Related Work

Influence Slot Selection

• Submodular Graph Methods: Methods based on pruned submodular graphs
• Branch-and-Bound Framework: Exact algorithm framework
• Greedy Solutions: Greedy algorithms based on marginal gains
• Cooperative Coevolutionary Methods: Co-operative Co-Evolutionary approach proposed by Wang et al.

Regret Minimization

• Local Search Methods: Local search solutions by Zhang et al.
• Regional Constraints: Regret minimization under regional influence constraints by Ali et al.

Theoretical Foundations

• Multi-Submodular Coverage Problem: Randomized bicriteria approximation algorithm by Chekuri et al.
• Continuous Greedy Algorithm: Continuous relaxation techniques for monotone submodular functions

Conclusions and Discussion

Main Conclusions

1. Problem Modeling: Successfully models multi-product billboard problems as multi-submodular coverage problems and their generalizations
2. Algorithm Effectiveness: Proposed algorithms perform well both theoretically and practically
3. Practical Value: Methods applicable to any multi-product outdoor advertising scenario

Limitations

1. Computational Complexity: Exponential time complexity of RA algorithm limits large-scale applications
2. Assumption Conditions: Assumes influence functions have submodularity property, which may not be fully satisfied in practice
3. Data Dependency: Requires accurate trajectory data and user product preference information
4. Static Model: Does not consider changes in demand and supply in dynamic environments

Future Directions

1. Dynamic Optimization: Consider time-varying influence requirements and user behavior
2. Online Algorithms: Develop online optimization algorithms for processing real-time data streams
3. Machine Learning Integration: Incorporate deep learning for predicting user interests and influence
4. Multi-objective Optimization: Simultaneously consider multiple objectives including cost, coverage, and fairness

In-Depth Evaluation

Strengths

1. Problem Importance: Addresses important problems in real commercial environments with clear application value
2. Theoretical Rigor: Provides complete theoretical analysis including approximation ratios and sample complexity
3. Algorithm Innovation: Cleverly applies continuous greedy and randomized rounding techniques to multi-product scenarios
4. Comprehensive Experiments: Conducts sufficient experimental validation on real datasets

Weaknesses

1. Scalability Limitations: Exponential complexity of RA algorithm limits application to large-scale problems
2. Simple Baselines: Baseline methods for comparison are relatively simple, lacking comparison with more advanced methods
3. Parameter Sensitivity: Insufficient analysis of sensitivity to key parameters (e.g., distance threshold λ)
4. Practical Constraints: Insufficient consideration of time constraints and competitive factors in real advertising deployment

Impact

1. Academic Contribution: Provides first systematic study of multi-product influence maximization problem
2. Practical Value: Directly applicable to outdoor advertising, digital signage, and other scenarios
3. Theoretical Significance: Extends the scope of submodular optimization theory in practical applications
4. Reproducibility: Provides detailed algorithm descriptions and experimental settings

Applicable Scenarios

1. Outdoor Advertising Networks: Multi-product deployment optimization for traditional billboard networks
2. Digital Signage Systems: Advertisement allocation for digital displays in shopping centers, airports, etc.
3. Transit Advertising: Advertisement slot allocation on public transportation vehicles
4. Online Advertising: Extensible to multi-product bidding and allocation in online advertising

References

The paper cites 22 related references, primarily including:

• Classical work on influence maximization (Kempe et al., 2003)
• Theoretical foundations of submodular optimization (Calinescu et al., 2007; Vondrák, 2007)
• Multi-submodular coverage problems (Chekuri et al., 2022)
• Related research on billboard advertising (Zhang et al., 2020, 2021)
• Probabilistic inequality theory (Hoeffding, 1963)

This paper makes important contributions at both theoretical and practical levels, providing systematic solutions to the multi-product influence maximization problem. Despite certain limitations, its innovation and practical value make it a significant advance in this field.