How to utilize an allocated budget effectively for branding and promotion of a commercial house is an important problem, particularly when multiple advertising media are available. There exist multiple such media, and among them, two popular ones are billboards and social media advertisements. In this context, the question naturally arises: how should a budget be allocated to maximize total influence? Although there is significant literature on the effective use of budgets in individual advertising media, there are hardly any studies examining budget allocation across multiple advertising media. To bridge this gap, this paper introduces the Budget Splitting Problem in Billboard and Social Network Advertisement. We introduce the notion of interaction effect to capture the additional influence due to triggers from multiple media of advertising. Using this notion, we propose a noble influence function Φ(,) that captures the total influence and shows that this function is non-negative, monotone, and non-bisubmodular. We introduce bi-submodularity ratio (γ) and generalized curvature (α) to measure how close a function is to being bi-submodular and how far a function is from being modular, respectively. We propose the Randomized Greedy and Two-Phase Adaptive Greedy approach, where the influence function is non-bisubmodular and achieves an approximation guarantee of (1/α)(1-e^(-γα)). We conducted several experiments using real-world datasets and observed that the proposed solution approach’s budget splitting leads to a greater influence than existing approaches.

Abstract Billboard Advertisement is a popular out-of-home advertising technique adopted by commercial houses. Companies own billboards and offer them to commercial houses on a payment basis. Given a database of billboards with slot information, we want to determine which k slots to choose to maximize the influence. We call this the Influential Billboard Slot Selection ( $$\textsc {IBSS}$$ IBSS ) Problem and pose it as a combinatorial optimization problem. We show that the influence function considered in this paper is non-negative, monotone, and submodular. The incremental greedy approach based on the marginal gain computation leads to a constant factor approximation guarantee. However, this method scales very poorly when the size of the problem instance is very large. To address this, we propose a spatial partitioning and pruned submodularity graph-based approach divided into the following three steps: pre-processing, pruning, and selection. We analyze the proposed solution approaches to understand their time, space requirements, and performance guarantees. We conduct extensive experiments with real-world datasets and compare the performance of the proposed solution approaches with the available baseline methods. We observe that the proposed approaches lead to more influence than all the baseline methods within a reasonable computational time.

Social media advertisement has emerged as an effective approach to promoting commercial house brands. Hence, many of them have started using this medium to maximize the influence among the users and create a customer base. In recent times, several companies have emerged as influence providers, providing a certain number of views based on the budget provided by a commercial house. In this process, the influence provider tries to exploit the information diffusion phenomenon of a social network. In this problem, the challenge is how to allocate the seed nodes among the advertisers so that the regret of the allocation is minimized. The input to the problem is a set of advertisers with their respective influence, demand, and budget, a social network along with the selection cost of the users, and the goal here is to allocate the seed nodes among the advertisers that minimize the regret. In this context, we introduce a noble regret model for social media advertisement. Two efficient heuristic solution approaches have been proposed. Both methodologies have been analyzed to understand their time and space requirements. The proposed solution approaches have been implemented with real-world social network datasets, and a number of experiments have been conducted. From the experiments, we have observed that the proposed solution approaches lead to the allocation of seed nodes, resulting in much less regret than the baseline methods.

Now-a-days, billboard advertisement has emerged as an effective outdoor advertisement technique. In this case, a commercial house approaches an influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider can satisfy this then they will receive the full payment else a partial payment. If the influence provider provides more or less than the demand then certainly this is a loss to them. This is formalized as ‘Regret’ and the goal of the influence provider will be to minimize the ‘Regret’. In this paper, we propose simple and efficient solution methodologies to solve this problem. Efficiency and effectiveness have been demonstrated by experimentation.