Optimizing impression counts for outdoor advertising

• Main Authors: ZHANG, Yipeng, LI, Yuchen, BAO, Zhifeng, MO, Songsong, ZHANG, Ping
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Outdoor Advertising; Influence Maximization; Moving Trajectory; Non-submodularity; Logistic Function; Advertising and Promotion Management; Computer Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4617; https://ink.library.smu.edu.sg/context/sis_research/article/5620/viewcontent/p1790_zhang.pdf
• Institution: Singapore Management University

In this paper we propose and study the problem of optimizing theinfluence of outdoor advertising (ad) when impression counts aretaken into consideration. Given a database U of billboards, each ofwhich has a location and a non-uniform cost, a trajectory databaseT and a budget B, it aims to find a set of billboards that has themaximum influence under the budget. In line with the advertisingconsumer behavior studies, we adopt the logistic function to takeinto account the impression counts of an ad (placed at differentbillboards) to a user trajectory when defining the influence measurement. However, this poses two challenges: (1) our problemis NP-hard to approximate within a factor of O(|T |1−ε) for anyε > 0 in polynomial time; (2) the influence measurement is nonsubmodular, which means a straightforward greedy approach isnot applicable. Therefore, we propose a tangent line based algorithm to compute a submodular function to estimate the upperbound of influence. Henceforth, we introduce a branch-and-boundframework with a θ-termination condition, achieving θ2(1 − 1/e)approximation ratio. However, this framework is time-consumingwhen |U| is huge. Thus, we further optimize it with a progressive pruning upper bound estimation approach which achievesθ2(1 − 1/e − ϵ) approximation ratio and significantly decreases therunning-time. We conduct the experiments on real-world billboardand trajectory datasets, and show that the proposed approachesoutperform the baselines by 95% in effectiveness. Moreover, theoptimized approach is around two orders of magnitude faster thanthe original framework.