Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2021

Abstract

Influence maximization has been studied extensively from the perspective of the influencer. However, the influencer typically purchases influence from a provider, for example in the form of purchased advertising. In this paper, we study the problem from the perspective of the influence provider. Specifically, we focus on influence providers who sell Out-of-Home (OOH) advertising on billboards. Given a set of requests from influencers, how should an influence provider allocate resources to minimize regret, whether due to forgone revenue from influencers whose needs were not met or due to over-provisioning of resources to meet the needs of influencers? We formalize this as the Minimizing Regret for the OOH Advertising Market problem (MROAM). We show that MROAM is both NP-hard and NP-hard to approximate within any constant factor. The regret function is neither monotone nor submodular, which renders any straightforward greedy approach ineffective. Therefore, we propose a randomized local search framework with two neighborhood search strategies, and prove that one of them ensures an approximation factor to a dual problem of MROAM. Experiments on real-world user movement and billboard datasets in New York City and Singapore show that on average our methods outperform the baselines in effectiveness by five times.

Keywords

Outdoor advertising, Regret minimization, Influence provider

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

The proceedings of International Conference on Management of Data, Oct 20-25

First Page

2115

Last Page

2127

Identifier

https://dl.acm.org/doi/10.1145/3448016.3457257

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.1145/3448016.3457257

Download

Share

COinS