Optimizing Impression Counts for Outdoor Advertising

ABSTRACT

In this paper we propose and study the problem of optimizing the influence of outdoor advertising (ad) when impression counts are taken into consideration. Given a database U of billboards, each of which has a location and a non-uniform cost, a trajectory database T and a budget B, it aims to find a set of billboards that has the maximum influence under the budget. In line with the advertising consumer behavior studies, we adopt the logistic function to take into account the impression counts of an ad (placed at different billboards) to a user trajectory when defining the influence measurement. However, this poses two challenges: (1) our problem is NP-hard to approximate within a factor of O(|T|^1-ε) for any ε>0 in polynomial time; (2) the influence measurement is non-submodular, which means a straightforward greedy approach is not applicable. Therefore, we propose a tangent line based algorithm to compute a submodular function to estimate the upper bound of influence. Henceforth, we introduce a branch-and-bound framework with a θ-termination condition, achieving θ2/(1 - 1/e) approximation ratio. However, this framework is time-consuming when |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 the running-time. We conduct the experiments on real-world billboard and trajectory datasets, and show that the proposed approaches outperform the baselines by 95% in effectiveness. Moreover, the optimized approach is around two orders of magnitude faster than the original framework.

References

1. Penneco Outdoor Advertising. 2016. Billboard Statistics. https://www.pennecooutdoor.com/billboard-statistics
2. Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. 2013. Local-Search based Approximation Algorithms for Mobile Facility Location Problems. In SODA. SIAM, 1607--1621.
3. Christoph Ambü hl, Monaldo Mastrolilli, and Ola Svensson. 2011. Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut. SIAM J. Comput., Vol. 40, 2 (2011), 567--596.
4. Margaret C Campbell and Kevin Lane Keller. 2003. Brand familiarity and advertising repetition effects. Journal of consumer research, Vol. 30, 2 (2003), 292--304.
5. Can Chen, Junming Liu, Qiao Li, Yijun Wang, Hui Xiong, and Shanshan Wu. 2017. Warehouse Site Selection for Online Retailers in Inter-Connected Warehouse Networks. In ICDM. IEEE, 805--810.
6. Farhana Murtaza Choudhury, J. Shane Culpepper, Zhifeng Bao, and Timos Sellis. 2018. Finding the optimal location and keywords in obstructed and unobstructed space. VLDB J., Vol. 27, 4 (2018), 445--470.
7. Gershon Feder, Richard E Just, and David Zilberman. 1985. Adoption of agricultural innovations in developing countries: A survey. Economic development and cultural change, Vol. 33, 2 (1985), 255--298.
8. Gerald J Gorn and Marvin E Goldberg. 1980. Children's responses to repetitive television commercials. Journal of Consumer Research, Vol. 6, 4 (1980), 421--424.
9. William H Greene. 2003. Econometric analysis .Pearson Education India.
10. Johny K Johansson. 1979. Advertising and the S-curve: A new approach. Journal of Marketing Research (1979), 346--354.
11. Samir Khuller, Anna Moss, and Joseph Naor. 1999. The Budgeted Maximum Coverage Problem. Inf. Process. Lett., Vol. 70, 1 (1999), 39--45.
12. LAMAR. 2017. National Rate Card. http://apps.lamar.com/demographicrates/content/salesdocuments/nationalratecard.xlsx
13. Sang Yup Lee. 2014. Examining the factors that influence early adopters' smartphone adoption: The case of college students. Telematics and Informatics, Vol. 31, 2 (2014), 308--318.
14. Guoliang Li, Shuo Chen, Jianhua Feng, Kian-Lee Tan, and Wen-Syan Li. 2014. Efficient location-aware influence maximization. In SIGMOD. ACM, 87--98.
15. Shi Li. 2019. On Facility Location with General Lower Bounds. In SODA. SIAM, 2279--2290.
16. John DC Little. 1979. Aggregate advertising models: The state of the art. Operations research, Vol. 27, 4 (1979), 629--667.
17. Dongyu Liu, Di Weng, Yuhong Li, Jie Bao, Yu Zheng, Huamin Qu, and Yingcai Wu. 2017. SmartAdP: Visual Analytics of Large-scale Taxi Trajectories for Selecting Billboard Locations. IEEE Trans. Vis. Comput. Graph., Vol. 23, 1 (2017), 1--10.
18. Yubao Liu, Raymond Chi-Wing Wong, Ke Wang, Zhijie Li, Cheng Chen, and Zitong Chen. 2013. A new approach for maximizing bichromatic reverse nearest neighbor search. Knowl. Inf. Syst., Vol. 36, 1 (2013), 23--58.
19. Prashant Malaviya. 2007. The moderating influence of advertising context on ad repetition effects: The role of amount and type of elaboration. Journal of Consumer Research, Vol. 34, 1 (2007), 32--40.
20. M. Teresa Melo, Stefan Nickel, and Francisco Saldanha-da-Gama. 2006. Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Computers & OR, Vol. 33 (2006), 181--208.
21. M. Teresa Melo, Stefan Nickel, and Francisco Saldanha-da-Gama. 2009. Facility location and supply chain management - A review. European Journal of Operational Research, Vol. 196, 2 (2009), 401--412.
22. George A Miller. 1956. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological review, Vol. 63, 2 (1956), 81.
23. Kristian S Palda. 1965. The measurement of cumulative advertising effects. The Journal of Business, Vol. 38, 2 (1965), 162--179.
24. William Sierzchula, Sjoerd Bakker, Kees Maat, and Bert Van Wee. 2014. The influence of financial incentives and other socio-economic factors on electric vehicle adoption. Energy Policy, Vol. 68 (2014), 183--194.
25. Julian L Simon and Johan Arndt. 1980. The shape of the advertising response function. Journal of Advertising Research (1980).
26. Jennifer Taylor, Rachel Kennedy, and Byron Sharp. 2009. Is once really enough? Making generalizations about advertising's convex sales response function. Journal of Advertising Research, Vol. 49, 2 (2009), 198--200.
27. Gerard J Tellis. 1988. Advertising exposure, loyalty, and brand purchase: A two-stage model of choice. Journal of marketing research (1988), 134--144.
28. Kenneth E Train. 2009. Discrete choice methods with simulation .Cambridge university press.
29. Demetrios Vakratsas, Fred M Feinberg, Frank M Bass, and Gurumurthy Kalyanaram. 2004. The shape of advertising response functions revisited: A model of dynamic probabilistic thresholds. Marketing Science, Vol. 23, 1 (2004), 109--119.
30. Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, and Gao Cong. 2018. Reverse k Nearest Neighbor Search over Trajectories. IEEE Trans. Knowl. Data Eng., Vol. 30, 4 (2018), 757--771.
31. Raymond Chi-Wing Wong, M. Tamer Ö zsu, Philip S. Yu, Ada Wai-Chee Fu, and Lian Liu. 2009. Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor. PVLDB, Vol. 2, 1 (2009), 1126--1137.
32. Ping Zhang, Zhifeng Bao, Yuchen Li, Guoliang Li, Yipeng Zhang, and Zhiyong Peng. 2018. Trajectory-driven Influential Billboard Placement. In SIGKDD. ACM, 2748--2757.
33. Zenan Zhou, Wei Wu, Xiaohui Li, Mong-Li Lee, and Wynne Hsu. 2011. MaxFirst for MaxBRkNN. In ICDE. IEEE, 828--839.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial optimization