Tag-specific Regret Minimization Problem in Outdoor Advertising
This work tackles a combinatorial optimization problem for influence providers in outdoor advertising, aiming to minimize regret and balance allocations, which is an incremental improvement to existing allocation strategies.
This paper addresses the problem of allocating advertising content (tags) to outdoor billboards to meet influence demand within budget constraints, aiming to minimize total regret. The authors formalize this as the Tag-specific Regret Minimization in Outdoor Advertising (TRMOA) problem, proving it NP-hard and inapproximable within a constant factor, and propose fairness-aware greedy, randomized greedy, and local search algorithms.
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.