Balanced Popularity in Multi-Product Billboard Advertisement
Dildar Ali, Suman Banerjee, Yamuna Prasad · 2025
Read Balanced Popularity in Multi-Product Billboard Advertisement by Dildar Ali, Suman Banerjee, Yamuna Prasad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20600.txt.
Introduction
Dildar Ali, Suman Banerjee, and Yamuna Prasad study a multi-product version of billboard slot selection where balance between products matters. An advertiser promotes several products with a separate budget for each, choosing slots so total influence is maximized while the influence gap between any two products stays below a given threshold. Influence is measured against traveler trajectories and a billboard database, and cost per product must respect its budget.
The authors prove the balanced popularity problem is NP-hard to solve optimally. They formulate it as a linear program and apply relaxation with randomized rounding, and they also propose a greedy heuristic with a balance correction step. A number of experiments with real-style data evaluate and compare the proposed solution approaches.
Catalog record
| CREATOR | Dildar Ali, Suman Banerjee, Yamuna Prasad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Balanced Popularity in Multi-Product Billboard Advertisement Dildar Ali, Suman Banerjee, Yamuna Prasad Abstract The billboard advertisement has emerged as an effective out-of-home advertisement technique where the objective is to choose a limited number of slots to play some advertisement content (e.g., animation, video, etc.) with the hope that the content will be visible to a large number of travelers, and this will be helpful to earn more revenue. In this paper, we study a variant of the influential slot selection problem where the advertiser wants to promote multiple products. Formally, we call this problem the Multi-Product Influence Maximization Problem for the Balanced Popularity Problem. The input to our problem is a trajectory and a billboard database, as well as a budget for each product. The goal here is to choose a subset of slots for each product such that the aggregated influence of all the products gets maximized subject to the following two constraints: total selection cost for each product is less than or equal to the allocated budget for that product, and the difference between the influence for any two products is less than or equal to a given threshold. We show that the problem is NP-hard to solve optimally. We formulate this problem as a linear programming problem and use linear programming relaxation with randomized rounding. Further, we propose a greedy-based heuristic with balance correction to solve this problem. We conduct a number of experiments with real-world trajectory and billboard datasets, and the results are reported. From the reported results, we observe that the proposed solution approaches lead to more influence compared to many baseline methods. 1 Introduction Recently, Billboard Advertisement has emerged as an effective out-of-home advertising technique due to the guaranteed return on investment 1 1 1 https://www.lamar.com/howtoadvertise/Research/ . In a billboard advertisement, a number of digital billboards are placed across popular places in a city, and the advertisement contents (e.g., animation, video, etc.) are played with the hope that the content will be observed by many people. This is a popular out-of-home advertisement technique that is helpful to reach a large audience with a low budget to create influence and awareness of the brand. Eventually, a little investment in advertising may lead to a large revenue with high probability. Background. To our knowledge, Zhang et al. [ 14 , 15 ] are the first to introduce the influence maximization problem in billboard advertising. This problem has been studied in the literature, and a number of solution methodologies have been proposed, such as the graph-based pruned-submodularity approach [ 1 ] , the spatial clustering approach [ 2 ] , the branch-and-bound approach [ 3 , 16 ] , and many more. Wang et al. [ 13 ] introduce the problem of finding the k best advertising units in billboard advertisements. There also exists literature in the context of advertising on billboards [ 7 , 6 ] and social networks [ 11 ] that select tags and slots jointly. Deviating from the influence maximization, there exists literature [ 17 , 4 , 8 ] that considers regret minimization in billboard advertising. In practice, an e-commerce house has multiple products to advertise. However, to our knowledge, there is no literature that considers slot selection for multiple products. Hence, in this paper, we address the Multi-Product Influence Maximization Problem for the Balanced Popularity Problem. Motivation. Consider the scenario where a commercial house wants to promote more than one product through billboard advertising. Different products will have different features, and hence it may not be meaningful to promote all the products to the same set of people. To make the campaign more effective, it is important to select slots that cover the people who are more likely to like the product. In this paper, we study the problem of selecting slots for multiple products where the goal is to maximize the aggregated influence for all products. However, it is important to observe that it may not be beneficial for the commercial house if there is a significant difference in influence between any two products. Because if for any product its influence is very low compared to another product, then the expected sales of the product will be low, and the initial investment of the commercial house for launching the product will go in vain. As a remedy, the commercial house may wish to choose slots in such a way as to lead to a balanced influence for all the products. Our Contribution. To the best of our knowledge, this problem has not been studied previously, and we make the following contributions. • We study the noble problem called the Multi-Product Influence Maximization Problem for the Balanced Popularity problem for which there is no literature. • We formulate this problem as a linear programming problem and use linear programming relaxation with randomized rounding. Further, we propose a greedy-based heuristic with balance correction to solve this problem. • We conducted experiments with real-world trajectory and billboard datasets to show the effectiveness and efficiency of the proposed solution approach. Organization of the Paper The rest of the paper has been organized as follows. Section 2 describes the background information and defines the problem formally. The proposed solution approaches have been described in Section 3 . Section 4 describes the experimental evaluation of the proposed solution approaches. Section 5 describes the concluding remarks of our study. 2 Background and Problem Definition Trajectory and Billboard Database. A trajectory database contains the location information of a set of people in a city across different time stamps. In our problem, a trajectory database \mathcal{D} contains tuples of the form (u_{i},\texttt{loc},[t_{a},t_{b}],\mathcal{P}(u_{i})) and this signifies that the person u_{i} is at the location loc for the duration t_{a} to t_{b} . Here, \mathcal{P}(u_{i}) denotes the set of products in which user u_{i} will be interested. For any person u_{i} , loc_{[t_{x},t_{y}]}(u_{i}) denotes the locations of u_{i} during the time interval [t_{x},t_{y}] . Let \mathcal{U} denote the set of people whose movement data is contained in \mathcal{D} . Let, T_{1}=\underset{\tau\in\mathcal{D}}{min}\ t_{a} and T_{2}=\underset{t\in\mathcal{D}}{max}\ t_{b} and we say that the trajectory database \mathcal{D} contains the movement data from time stamp T_{1} to T_{2} . A billboard database \mathbb{B} contains the information about billboard slots. Typically, this contains the tuples of the following form (b_{id},s_{id},\texttt{loc},\texttt{duration}) where b_{id} and s_{id} denote the billboard id and slot id. The loc and duration signify the billboard’s location and the slot’s duration. Billboard Advertisement. Let a set of m billboards \mathcal{B}=\{b_{1},b_{2},\ldots,b_{m}\} be placed in different locations of a city. We assume that all the billboards can be leased for a multiple of a fixed duration \Delta , which is called a ‘slot’ and has been stated in Definition 1 . Definition 1 (Billboard Slot) A billboard slot is defined by a tuple consisting of two entities, the billboard ID and the duration, that is, (b_{id},[t,t+\Delta]) . The set of all billboard slots is denoted by \mathcal{BS} , i.e., \mathcal{BS}=\{(b_{i},[t,t+\Delta]):i\in\{1,2,\ldots,m\}\text{ and }t\in\{T_{1},T_{1}+\Delta,T_{1}+2\Delta,\ldots,T_{2}-\Delta\}\} . It can be observed that |\mathcal{BS}|=m\cdot\frac{T}{\Delta} where T=T_{2}-T_{1} . For simplicity, we assume that T is perfectly divisible by \Delta . For any slot s_{j}\in\mathcal{BS} , b_{s_{j}} denotes the corresponding billboard and [t^{s}_{s_{j}},t^{f}_{s_{j}}] denotes the time interval for the slot s_{j} where t^{f}_{s_{j}}=t^{s}_{s_{j}}+\Delta .