Dildar Ali

Dildar Ali, Ansh Jasrotia, Abishek Salaria et al.

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 \textsc{Budget Splitting Problem in Billboard and Social Network Advertisement}. We introduce the notion of \emph{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 \emph{bi-submodularity ratio $(γ)$} and \emph{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 $\frac{1}α\left(1-e^ {-γα} \right)$. 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.

Dildar Ali, Suman Banerjee, Yamuna Prasad

Creating and maximizing influence among the customers is one of the central goals of an advertiser, and hence, remains an active area of research in recent times. In this advertisement technique, the advertisers approach an influence provider for a specific number of views of their content on a payment basis. Now, if the influence provider can provide the required number of views or more, he will receive the full, else a partial payment. In the context of an influence provider, it is a loss for him if he offers more or less views. This is formalized as 'Regret', and naturally, in the context of the influence provider, the goal will be to minimize this quantity. In this paper, we solve this problem in the context of billboard advertisement and pose it as a discrete optimization problem. We propose four efficient solution approaches for this problem and analyze them to understand their time and space complexity. We implement all the solution methodologies with real-life datasets and compare the obtained results with the existing solution approaches from the literature. We observe that the proposed solutions lead to less regret while taking less computational time.

Dildar Ali, Abishek Salaria, Ansh Jasrotia et al.

Recently, out-of-home advertising has become a popular marketing technique, due to its higher return on investment. E-commerce houses approach the influence provider to achieve effective advertising through their tags (advertising content), influence demand, and budgets. The influence provider's goal will be to make proper tag allocations, meet the required influence demand within the budget constraint, and minimize total regret. We formalize this as a combinatorial optimization problem and refer to it as \textsc{Tag-specific Regret Minimization in Outdoor Advertising (TRMOA)}. We show that TRMOA is NP-hard and inapproximable within a constant factor. The regret model we consider is non-monotone and non-submodular, and the simple greedy approach is ineffective. We introduce a fairness-aware greedy round-robin approach that reduces regret with balanced allocation across advertisers. To improve, we also introduce randomized greedy and local search algorithms. We have experimented with all the methodologies using real-world trajectory and billboard datasets to show the effectiveness and efficiency of the solution methodologies.

Aditi Anand, Suman Banerjee, Dildar Ali

In Reinforcement Learning (abbreviated as RL), an agent interacts with the environment via a set of possible actions, and a reward is generated from some unknown distribution. The task here is to find an optimal set of actions such that the reward after a certain time step gets maximized. In a traditional setup, the reward function in an RL Problem is considered additive. However, in reality, there exist many problems, including path planning, coverage control, etc., the reward function follows the diminishing return, which can be modeled as a submodular function. In this paper, we study a variant of the RL Problem where the reward function is submodular, and our objective is to find an optimal policy such that this reward function gets maximized. We have proposed a pruned submodularity graph-based approach that provides a provably approximate solution in a feasible computation time. The proposed approach has been analyzed to understand its time and space requirements as well as a performance guarantee. We have experimented with a benchmark agent-environment setup, which has been used for similar previous studies, and the results are reported. From the results, we observe that the policy obtained by our proposed approach leads to more reward than the baseline methods.