Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2019

Abstract

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.

Keywords

Outdoor Advertising, Influence Maximization, Moving Trajectory, Non-submodularity, Logistic Function

Discipline

Advertising and Promotion Management | Computer Engineering

Research Areas

Data Science and Engineering

Publication

Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, Alaska, 2019 August 4-8

First Page

1205

Last Page

1215

Identifier

10.1145/3292500.3330829

City or Country

Anchorage, Alaska

Additional URL

https://doi.org/10.1145/3292500.3330829

Download

Share

COinS