{"ID":2857373,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.09050","arxiv_id":"2510.09050","title":"Multi-product Influence Maximization in Billboard Advertisement","abstract":"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.","short_abstract":"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 br...","url_abs":"https://arxiv.org/abs/2510.09050","url_pdf":"https://arxiv.org/pdf/2510.09050v1","authors":"[\"Dildar Ali\",\"Rajibul Islam\",\"Suman Banerjee\"]","published":"2025-10-10T06:39:50Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DB\"]","methods":"[]","has_code":false}