11institutetext: Department of Computer Science and Engineering,
Indian Institute of Technology Jammu
Jammu & Kashmir-181221, India.
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Influential Billboard Slot Selection under Zonal Influence Constraint

Dildar Ali  Suman Banerjee  Yamuna Prasad

###### Abstract

Given _billboard_ and _trajectory database_ , finding a limited number of
billboard slots for maximizing the influence is an important problem in the
context of _billboard advertisement_. Most of the existing literature focused
on the influential slot selection problem without considering any specific
zonal influence constraint. To bridge this gap in this paper, we introduce and
study the Influential Billboard Slot Selection Problem Under Zonal Influence
Constraint. We propose a simple greedy approach to solve this problem. Though
this method is easy to understand and simple to implement due to the excessive
number of marginal gain computations, this method is not scalable. We design a
branch and bound framework with two bound estimation techniques that divide
the problem into different zones and integrate the zone-specific solutions to
obtain a solution for the whole. We implement both the solution methodologies
with real-world billboard and trajectory datasets and several experiments have
been reported. We compare the performance of the proposed solution approaches
with several baseline methods. The results show that the proposed approaches
lead to more effective solutions with reasonable computational overhead than
the baseline methods.

###### Keywords:

Billboard Database Trajectory Database Zonal Influence Budget Influence
Maximization.

##  1 Introduction

_Billboard Advertising_ has become effective out-of-home marketing strategy,
offering excellent returns on investment
111https://topmediadvertising.co.uk/billboard-advertising-statistics/. Several
commercial houses have emerged as effective players in this domain. This area
has grown tremendously in the last decade, and by the end of 2024, it has
become $410.82$ billion dollar industry
222https://www.thebusinessresearchcompany.com/report/billboard-and-outdoor-
advertising-global-market-report. To make an effective billboard
advertisement, it is always important to choose most billboard slots that will
reach a large number of people. However, each billboard slot is associated
with some cost, which means if a commercial house hires a particular slot, a
pre-specified amount of money needs to be paid to the influence provider. As
per the marketing literature reports, a commercial house spends around
$7-10\%$ of its annual revenue for advertising
purposes333https://www.lamar.com/howtoadvertise/Research/. So, it is an
important question: given the information about billboard slots and
corresponding costs, how can we select a limited number of them? This problem
is called the Billboard Slot Selection Problem.

#### Background.

To the best of our knowledge, Zhang et al. [8] were the first to study the
billboard advertisement problem. Further, Zhang et al. [10] find a set of
billboards with maximum influence under a budget when impression counts are
considered. Zhang et al. [9] further extend their previous work [8] to find a
set of most influential billboards under a budget constraint. Wang et al.[6]
find $k$ best advertising units which maximize the influence spread in
targeted advertising. Similarly, Wang et al.[5] study the problem of targeted
influence maximization under a limited budget constraint. Deviating from the
influence maximization, some literature exists [3, 4, 11] on regret
minimization in the context of billboard advertisements. To the best of our
knowledge, none of the studies have considered the budget associated with a
billboard slot, unlike the study by Ali et al.[1, 2]. Also, none of the
studies have considered the concept of zonal influence constraint. Now, we
describe the motivation behind this constraint.

#### Motivation.

In all the previous studies [8, 1, 10, 9], It is assumed that each zone in a
city is equally meaningful to an advertiser during the selection of slots.
However, this is not always true in real-life scenarios [3]. Let’s consider
the zone-specific population information of a city is known to the advertiser.
Now, it is meaningless to advertise a highly expensive product in a
demographic zone where economically backward classes people live. Because they
may not buy the product, investing money to advertise such a product by the
advertiser is totally waste. Hence, we divide the city into several zones
based on the demographic information. Now, the advertisers have zonal
influence demand along with the budget, and the influence provider must
fulfill this. So, studying the Billboard Slot Selection Problem under zonal
influence constraint is important.

#### Our Contributions.

This paper introduces the problem of selecting influential billboard slots
under zonal influence constraint. We call this problem Influential Billboard
Slot Selection under Zonal Influence Constraint (IBSSP). To the best of our
knowledge, this is the first study in this direction. The key contributions of
this paper are as follows:

  * •

We introduce and formulate this problem as a discrete optimization problem and
show this problem as NP-hard to approximate within a constant factor.

  * •

We propose a simple greedy and branch and bound approach with two bound
estimation techniques to solve this problem.

  * •

We substantiate our claim regarding the efficiency and effectiveness of the
proposed solutions by experimental evaluations with real-world datasets.

#### Organization of the Paper.

The rest of the paper is organized as follows. Section 2 describes the
background of our problem and defines it formally. The proposed solution
approaches have been described in Section 3. Section 4 contains the
experimental evaluation of the proposed solution approaches. Finally, Section
5 concludes our study and mentions future research directions.

##  2 Background and Problem Definition

Consider a set of $m$ digital billboards
$\mathbb{B}=\\{b_{1},b_{2},\ldots,b_{m}\\}$ are placed across a geographical
region of interest. Each one is operated for the duration $[T_{1},T_{2}]$ and
we denote $T=T_{2}-T_{1}$. Each billboard is allocated slot-wise with the
duration of the slot equal to $\Delta$. Now, we define the notion of a
billboard slot.

######  Definition 1 (Billboard Slot)

Given a set of billboards and a fixed duration of slot $\Delta$, a billboard
slot is defined by a tuple $(bs_{i},[t,t+\Delta])$ where $bs_{i}\in\mathbb{B}$
and $t\in\\{T_{1},T_{1}+\Delta+1,T_{1}+2\Delta+1,\ldots,T_{2}-\Delta+1\\}$.

It can be observed that the number of billboard slots will be equal to
$m\cdot\frac{T}{\Delta}$. Now, each billboard slot is associated with some
cost, and this is formalized by the cost function $\mathcal{C}$ that maps each
billboard slot to its associated cost
$\mathcal{C}(bs_{i})~{}\forall~{}bs_{i}\in\mathcal{BS}$, i.e.,
$\mathcal{C}:\mathcal{BS}\longrightarrow\mathbb{Z}^{+}$. Now, a subset of the
slots can be chosen with a fixed budget of $\mathcal{B}$. Next, we define the
influence of a subset of billboard slots in Definition 2.

######  Definition 2 (Influence of Billboard Slots)

Given a trajectory and billboard database and a subset of billboard slots
$\mathcal{S}\subseteq\mathcal{BS}$, the influence of the billboard slots is
given by Equation No. 1.

$\mathcal{I}(\mathcal{S})=\underset{u_{j}\in\mathcal{U}}{\sum}\
[1-\underset{bs_{i}\in\mathcal{S}}{\prod}(1-Pr(bs_{i},u_{j}))]$ (1)

Here, $\mathcal{I}()$ is the influence function that maps all possible subsets
of the billboard slots to its expected influence, i.e.,
$\mathcal{I}:2^{\mathcal{BS}}\longrightarrow\mathbb{R}_{0}^{+}$ with
$\mathcal{I}(\emptyset)=0$. Now, consider the geographical region under
consideration is denoted by $\mathcal{Z}$, and this is divided into $\ell$
many zones $\mathcal{Z}=\\{z_{1},z_{2},\ldots,z_{\ell}\\}$. Consider an
advertiser $a_{i}$ wants to choose a subset of billboard slots within the
allocated budget $\mathcal{B}$ such that zonal influence demand is satisfied.
Let, for any zone $z_{i}\in\mathcal{Z}$ the influence requirement is
$\sigma_{i}$. The influence of the billboard slot subset $\mathcal{S}$ subject
to the zone $z_{i}$ is denoted by $\mathcal{I}_{z_{i}}(\mathcal{S})$ and
$\mathcal{I}(\mathcal{S})=\underset{z_{i}\in\mathcal{Z}}{\sum}\
\mathcal{I}_{z_{i}}(\mathcal{S})$. So the problem becomes: “ Given a billboard
database $\mathbb{B}$, trajectory database $\mathbb{T}$ and a cost function
$\mathcal{C}$, the problem of Influential Billboard Slot Selection with Zonal
Influence Constraint asks to choose a subset of the billboard slots
$\mathcal{S}$ such that the total selection cost is less than the budget,
i.e., $\underset{b_{i}\in\mathcal{S}}{\sum}\mathcal{C}(b_{i})\leq\mathcal{B}$
and the zonal influence constraint for all the zones are satisfied, i.e.,
$\mathcal{I}_{z_{i}}(\mathcal{S})\geq\sigma_{i}$ for all $i\in[\ell]$ such
that the influence is maximized". Now, we define the zonal influence
constraint in Definition 3.

######  Definition 3 (Zonal Influence Constraint)

Let $\mathbb{BS}_{a_{i}}$ be the set of allocated billboard slots to the
advertiser $a_{i}$ and $\mathbb{BS}^{z_{j}}_{a_{i}}$ $\subseteq$
$\mathbb{BS}_{a_{i}}$, contains the billboard slots associated with zone
$z_{j}$. Now, we can say this allocation satisfies the zonal influence
constraint for zone $z_{j}$ if and only if
$\mathcal{I}(\mathbb{BS}^{z_{j}}_{a_{i}})\geq\sigma^{j}_{i}$.

Next, this problem can be formally stated as follows:

Slot Selection in Billboard Advertisement Problem Input: Billboard Slots set
$\mathcal{BS}$, Trajectory Database $\mathbb{T}$, Influence Function
$\mathcal{I}()$, Budget $\mathcal{B}$, Advertiser Database $\mathcal{A}$.
Problem: Find out a subset of billboard slots
$\mathcal{P}\subseteq\mathcal{BS}$, such that zonal influence demand is
satisfied and total influence is maximized.

The influence maximization problem without considering zonal influence
constraints in billboard advertisement has been studied by Zhang et al. [9],
and they had inapproximability results stated in Theorem 2.1.

###### Theorem 2.1

The Influential Billboard Slot Selection Problem Under Zonal Influence
Constraint is NP-hard and hard to approximate with a constant factor
algorithm.

This means the same inapproximability result also holds for our problem. Next,
in section 3, we discuss the proposed solution methodologies.

##  3 Proposed Solution Approach

###  3.1 Simple Greedy Allocation Scheme.

This kind of greedy approach has already been studied by Zhang et al. [9] for
influential billboard selection problems. Hence, we have extended the greedy
approach for our problem context, i.e., under zonal influence constraint. A
simple straight forward greedy approach for selecting billboard slots is
defined in Algorithm 1 (Line No. $1$ to $22$), which selects the billboard
slots that maximize the marginal influence gain to a candidate solution set
$\mathcal{P}$ to fulfill the zone-specific influence demand of an advertiser
until the budget $(\mathcal{B})$ is exhausted. However, a simple greedy
approach does not guarantee the approximation ratio due to budget constraints.
Hence, Line No. $23$ to $49$ is added with simple greedy to overcome the
drawback and guarantees an approximation ratio. Basically, the naive greedy
approach is used where the billboard slots are chosen based on the
individual’s highest influence value to solve the IBSSP problem.

Data: Trajectory Database $\mathbb{T}$, Billboard Database $\mathbb{B}$,
Advertiser Database $\mathcal{A}$, and the Influence Function $\mathcal{I}()$,
Zone Information, Budget $\mathcal{B}$, Zonal influence demand $\sigma$.

Result: A Billboard slot set $\mathcal{P}\subseteq\mathbb{BS}$ such that
$\mathcal{C}(\mathcal{P})\leq\mathcal{B}$

1

$\text{Initialize }\mathcal{K}\leftarrow\emptyset$,
$\mathcal{P}\leftarrow\emptyset$, $\mathcal{Q}\leftarrow\emptyset$,
$\mathcal{B}_{1}=\mathcal{B}_{2}=\mathcal{B}$;

2

3for  _each $z_{j}\in a_{z}$_ do

4 $\mathcal{S}\leftarrow\emptyset$;

5

6 while  _$\sigma_{z_{j}} >I(\mathcal{S})\text{ and
}\mathcal{BS}_{z_{j}}\neq\emptyset$_ do

7 $s^{*}\leftarrow\underset{s\in\mathcal{BS}_{z_{j}}}{\text{argmax}}\
\frac{\mathcal{I}(\mathcal{S}\cup\\{s\\})-\mathcal{I}(\mathcal{S})}{\mathcal{C}(\\{s\\})}$;

8

9 if  _$\mathcal{C}(\mathcal{S})+\mathcal{C}(\\{s^{*}\\})\leq\mathcal{B}_{1}$_
then

10 $\mathcal{S}\leftarrow\mathcal{S}\cup\\{s^{*}\\}$;

11 $\mathcal{BS}_{z_{j}}\leftarrow\mathcal{BS}_{z_{j}}\setminus\\{s^{*}\\}$;

12 $\mathcal{B}_{1}\leftarrow\mathcal{B}_{1}-\mathcal{C}(s^{*})$;

13

14 end if

15

16 end while

17 $\mathcal{P}\leftarrow\mathcal{P}\cup\\{\mathcal{S}\\}$;

18

19 end for

20$\mathcal{BS}\leftarrow\\{\mathcal{BS}_{z_{1}}\cup\mathcal{BS}_{z_{2}}\cup\ldots\cup\mathcal{BS}_{z_{l}}\\}$;

21 while  _$\mathcal{B}_{1} >0\text{ and }\mathcal{BS}\neq\emptyset$_ do

22 $s^{*}\leftarrow\underset{s\in\mathcal{BS}}{\text{argmax}}\
\frac{\mathcal{I}(\mathcal{S}\cup\\{s\\})-\mathcal{I}(\mathcal{S})}{\mathcal{C}(\\{s\\})}$;

23

24 if
_$\mathcal{C}(\mathcal{P})+\mathcal{C}(\\{s^{*}\\})\leq\mathcal{B}_{1}$_ then

25 $\mathcal{P}\leftarrow\mathcal{P}\cup\\{s^{*}\\}$;

26 $\mathcal{BS}\leftarrow\mathcal{BS}\setminus\\{s^{*}\\}$;

27 $\mathcal{B}_{1}\leftarrow\mathcal{B}_{1}-\mathcal{C}(s^{*})$;

28

29 end if

30

31 end while

32

33

34for  _each $z_{j}\in a_{z}$_ do

35 $\mathcal{K}\leftarrow\emptyset$;

36

37 while  _$\sigma_{z_{j}} >I(\mathcal{K})\text{ and
}\mathcal{BS}_{z_{j}}\neq\emptyset$_ do

38 $k^{*}\leftarrow\underset{s\in\mathcal{BS}_{z_{j}}}{\text{argmax}}\
\mathcal{I}(\mathcal{K}\cup\\{s\\})$;

39

40 if
_$\mathcal{C}(\mathcal{K})+\mathcal{C}(\\{k^{*}\\})\leq\mathcal{B}_{2}$_ then

41 $\mathcal{K}\leftarrow\mathcal{K}\cup\\{k^{*}\\}$;

42 $\mathcal{BS}_{z_{j}}\leftarrow\mathcal{BS}_{z_{j}}\setminus\\{k^{*}\\}$;

43 $\mathcal{B}_{2}\leftarrow\mathcal{B}_{2}-\mathcal{C}(k^{*})$;

44

45 end if

46

47 end while

48 $\mathcal{Q}\leftarrow\mathcal{Q}\cup\\{\mathcal{K}\\}$;

49

50 end for

51$\mathcal{BS}\leftarrow\\{\mathcal{BS}_{z_{1}}\cup\mathcal{BS}_{z_{2}}\cup\ldots\cup\mathcal{BS}_{z_{l}}\\}$;

52 while  _$\mathcal{B}_{2} >0\text{ and }\mathcal{BS}\neq\emptyset$_ do

53 $k^{*}\leftarrow\underset{s\in\mathcal{BS}}{\text{argmax}}\
\mathcal{I}(\mathcal{K}\cup\\{s\\})$;

54

55 if
_$\mathcal{C}(\mathcal{Q})+\mathcal{C}(\\{k^{*}\\})\leq\mathcal{B}_{2}$_ then

56 $\mathcal{Q}\leftarrow\mathcal{Q}\cup\\{k^{*}\\}$;

57 $\mathcal{BS}\leftarrow\mathcal{BS}\setminus\\{k^{*}\\}$;

58 $\mathcal{B}_{2}\leftarrow\mathcal{B}_{2}-\mathcal{C}(k^{*})$;

59

60 end if

61

62 end while

63if  _$\mathcal{I}(\mathcal{Q}) >\mathcal{I}(\mathcal{P})$_ then

64 return $\mathcal{Q}$;

65

66 end if

67else

68 return $\mathcal{P}$

69 end if

Algorithm 1 Simple Greedy Approach for Influential Billboard Slot Selection
Problem

#### Complexity Analysis.

In-Line No. $1$ initializing an empty sets
$\mathcal{K}$,$\mathcal{P}$,$\mathcal{Q}$ will take $\mathcal{O}(1)$ time. In-
Line No. $2$ for loop and Line No. $4$ while loop will execute for
$\mathcal{O}(\ell)$ and $\mathcal{O}(m)$ time, respectively. In-Line No. $5$,
computing influence will take $\mathcal{O}(2\cdot\ell\cdot m\cdot t)$ where
$t$ is the number of tuples in the trajectory database. Line No. $6$ to $10$
will execute for $\mathcal{O}(\ell\cdot m)$ time. Hence, Line No. $1$ to $14$
will take $\mathcal{O}(m^{2}\cdot\ell\cdot t^{2})$. Similarly, Line No. $15$
to $22$ will take $\mathcal{O}(m^{2}\cdot t)$. In Line No. $23$ to $35$ will
take $\mathcal{O}(m^{2}\cdot\ell\cdot t^{2})$ and Line No. $36$ to $49$ will
take $\mathcal{O}(m^{2}\cdot t)$ time to execute. So, Algorithm 1 will take
total $\mathcal{O}(m^{2}\cdot\ell\cdot t^{2}+m^{2}\cdot t)$ i.e.,
$\mathcal{O}(m^{2}\cdot\ell\cdot t^{2})$ time to execute. The extra space
taken by Algorithm 1 will be of $\mathcal{O}(\ell+m)$.

###  3.2 Branch and Bound Approach.

Although Simple Greedy achieves a constant approximation guarantee, executing
requires huge amounts of computational time. To overcome the drawback, we
introduce the Branch and Bound approach in Algorithm 2. We first initialize
$U_{G}$, $L_{G}$ and the max heap
$(\mathcal{P},\bar{\mathcal{P}},\mathcal{Y},\mathcal{U})$, where $\mathcal{P}$
is the solution set, $\bar{\mathcal{P}}$ is the set of unexplored billboard
slots, $\mathcal{Y}$ is the zone-specific influence demand, and $\mathcal{U}$
is the upper bound of the influence. The max heap $\mathcal{H}$ is ordered
based on the upper bound of influence $\mathcal{U}$. Hence, the heap will pop
the top entry, which has a maximum $\mathcal{U}$ value till $L_{G}<U_{G}$.
Further, as long as the budget constraint is satisfied, it will generate two
new branches $\mathcal{P}^{a}$ and $\mathcal{P}^{b}$. Initially,
$\mathcal{P}^{a}$ denotes the feasible slots set by adding $b$ while
$\mathcal{P}^{b}$ is the feasible slots set excluding $b$ (Lines $9$ \- $11$).
Now, based on the value of $\mathcal{P}^{a}$ (or $\mathcal{P}^{b}$) and
$\bar{\mathcal{P}}$ value the $BoundEstimation(.)$ or $FastBoundEstimation$
function will return $(\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a})$ or
$(\mathcal{P}^{c},L^{b},\mathcal{Y},\mathcal{U}^{b})$. In-Line No. $13$ if the
current satisfied influence demand $(L^{a})$ is greater than previous
satisfied demand $(L^{G})$ then update $L^{G}$ with $L^{a}$ and
$\hat{\mathcal{P}}$ with $\mathcal{P}^{c}$ as it may be the possible solution
set. Next, in Line No. $16$, if updated influence demand $(\mathcal{U}^{a})$
still greater than $L_{G}$, then insert that node into the max heap
$\mathcal{H}$ for further explorations. We do the same in Line No. $19$ to
$25$ for $\mathcal{S}^{b}$. We repeat the while loop for all the branches
until $L_{G}\geq U_{G}$.

Data: Trajectory Database $\mathbb{T}$, Billboard Database $\mathbb{B}$, and
the Influence Function $I()$, Zonal Demand $\mathcal{Y}$, Zone Info. $a_{z}$,
Budget $\mathcal{B}$.

Result: A Billboard slot set $\hat{\mathcal{P}}\subseteq\mathbb{BS}$ such that
$\mathcal{C}(\hat{\mathcal{P}})\leq\mathcal{B}$

1

2Initialize $\hat{\mathcal{P}}\leftarrow\emptyset$,
$\mathcal{P}\leftarrow\emptyset$,
$\bar{\mathcal{P}}\leftarrow\mathbb{BS},\mathcal{Y}=(\sigma_{z_{1}},\sigma_{z_{2}},\ldots\sigma_{z_{\ell}})$;

3 Initialize max heap
$\mathcal{H}\leftarrow(\mathcal{P},\bar{\mathcal{P}},\mathcal{Y},\mathcal{U})$;

4

5$L_{G}\leftarrow 0$, $U_{G}\leftarrow\infty$;

6 while  _$L_{G} <\theta.U_{G}$_ do

7 $(\mathcal{P},\bar{\mathcal{P}},\mathcal{Y},\mathcal{U})\leftarrow$ top of
$\mathcal{H}$;

8 $U_{G}\leftarrow\mathcal{U}$;

9 for  _each $b\in\bar{\mathcal{P}}$_ do

10 if  _$\mathcal{C}(\mathcal{P})$ \+ $\mathcal{C}(b)\leq\mathcal{B}$_ then

11 $\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\\{b\\}$;

12 $\mathcal{P}^{a}\leftarrow\mathcal{P}\cup\\{b\\}$;

13 $\mathcal{P}^{b}\leftarrow\mathcal{P}$;

14
$(\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a})\leftarrow\text{BoundEstimation}(\mathcal{P}^{a},\bar{\mathcal{P}},a_{z},\mathcal{Y})$;

15 if  _$L^{a} >L_{G}$_ then

16 $L_{G}\leftarrow L^{a}$, $\hat{\mathcal{P}}\leftarrow\mathcal{P}^{c}$;

17

18 end if

19 if  _$\mathcal{U}^{a} >L_{G}$_ then

20
$\mathcal{H}\leftarrow\mathcal{H}\cup(\mathcal{P}^{a},\bar{\mathcal{P}},\mathcal{Y},\mathcal{U}^{a})$;

21

22 end if

23
$(\mathcal{P}^{c},L^{b},\mathcal{Y},\mathcal{U}^{b})\leftarrow\text{BoundEstimation}(\mathcal{P}^{b},\bar{\mathcal{P}},a_{z},\mathcal{Y})$;

24 if  _$L^{b} >L_{G}$_ then

25 $L_{G}\leftarrow L^{b}$, $\hat{\mathcal{P}}\leftarrow\mathcal{P}^{c}$;

26

27 end if

28 if  _$\mathcal{U}^{b} >L_{G}$_ then

29
$\mathcal{H}\leftarrow\mathcal{H}\cup(\mathcal{P}^{b},\bar{\mathcal{P}},\mathcal{Y},\mathcal{U}^{b})$;

30

31 end if

32

33 end if

34

35 end for

36

37 end while

38return $\hat{\mathcal{P}}$;

Algorithm 2 Branch and Bound Approach for Influential Billboard Slot Selection
Problem

#### Complexity Analysis.

Now, we analyze the time and space requirements for Algorithm 2.
Initialization at Line No. $1,3$ will take $\mathcal{O}(1)$ time and
initialize max heap in Line No. $2$ will take $\mathcal{O}(m\cdot\log\cdot m)$
time. In-Line No. $4$ while loop will execute for $\mathcal{O}(n)$ till
$L^{G}<U^{G}$. To pick an element in Line No. $7$ will take $\mathcal{O}(1)$,
and Line No. $8$ to $11$ will take $\mathcal{O}(m)$ time to execute. In-Line
No. $12$ for each slot, it will take $\mathcal{O}(\ell\cdot m^{2}\cdot t)$
time to execute. Next, in Line No. $13$ to $15$ will take $\mathcal{O}(1)$
time and Line No. $16$ to $18$ will take $\mathcal{O}(m\cdot\log\cdot m)$
time. So, Line No. $12$ to $18$ will take $\mathcal{O}(\ell\cdot m^{2}\cdot
t+m\cdot\log\cdot m)$ time to execute. Similarly, Line No. $19$ to $25$ will
take $\mathcal{O}(\ell\cdot m^{2}\cdot t+m\cdot\log\cdot m)$ time in the worst
case. Hence, In Algorithm 2 will take total $\mathcal{O}(\ell\cdot m^{2}\cdot
t+m\cdot\log\cdot m)$ time to execute the while loop each time. The additional
space requirements for Algorithm 2 will be of $\mathcal{O}(m+\ell)$.

###  3.3  Fast Bound Estimation.

The Fast Bound Estimation approach is introduced in Algorithm 3 to generate
and explore the branches in each step. A key challenge is to find a tight
upper bound due to the overlap influence of the billboard slots. So, to
achieve this goal, we first allocate billboard slots
$\mathcal{P}^{c}=\\{b_{1},b_{2},\ldots b_{k}\\}$, where
$k\subseteq\mathcal{BS}$ based on the highest influence value till the budget
constraint is satisfied. Let’s assume $b^{extra}$ is the next billboard slot
with the highest influence value. Now, if we include $b^{extra}$ into
$\mathcal{P}^{c}$ total budget is exceeded, but if not included, we will lose
the cost $\mathcal{B}-\mathcal{C}(\mathcal{P}^{c})$. Therefore we add
$b^{extra}$ to get the upper bound, and it is calculated as
$\mathcal{U}^{a}\leftarrow\mathcal{I}(\mathcal{P}^{c})+[\mathcal{B}-\mathcal{C}(\mathcal{P}^{c})].\frac{\mathcal{I}(\mathcal{P}^{c}\cup~{}b^{extra})-\mathcal{I}(\mathcal{P}^{c})}{\mathcal{C}(b^{extra})}$.
This Algorithm starts by initializing $p^{*}$ and zone-specific influence
demand $\mathcal{Y}$. In-Line No. $2$ for loop will execute for all the zones
an advertiser has, and in Line, No. $3$ the while loop will run until the
budget is exhausted and zonal influence demands are satisfied. If the budget
and remaining influence demand are greater than zero, then Line No. $14$ to
$21$ will be executed to fulfill the demand. In-Line No. $23$ to $24$, the
lower and upper bound is calculated, and in Line No. $25$ $\mathcal{P}^{c}$,
$\mathcal{Y}$, $\mathcal{U}^{a}$ and $L^{a}$ is returned.

Data: $\mathcal{D}$, $\mathbb{BS}$, $I()$, $z_{j}$, $\mathcal{B}$,
$\mathcal{P}^{a}$, $\bar{\mathcal{P}}$, $\mathcal{Y}$.

Result: ($\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a}$)

1

$p^{*}\leftarrow\emptyset$, $\mathcal{P}^{c}\leftarrow\emptyset$;

2 for  _each $z_{j}\in a_{z}$_ do

3 while  _$\mathcal{C}(\mathcal{P}^{a})+\mathcal{C}(p^{*})\leq\mathcal{B}$ and
$\mathcal{I}(\mathcal{P}^{a}\cup\\{p^{*}\\})\leq\sigma_{z_{j}}$ and
$\bar{|\mathcal{P}|}\neq\emptyset$ _ do

4

5 $b\leftarrow\underset{s\in\bar{\mathcal{P}}}{argmax}\
\mathcal{I}((\mathcal{P}^{a}\cup\\{p^{*}\\})\cup\\{s\\})$;

6

7 if  _ $\mathcal{C}(\mathcal{P}^{a}\cup
p^{*})+\mathcal{C}(b)\leq\mathcal{B}$_ then

8 $p^{*}\leftarrow p^{*}\cup\\{b\\}$;

9 $\mathcal{B}\leftarrow\mathcal{B}-\mathcal{C}(b)$;

10

11 end if

12 $\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\\{b\\}$;

13

14 end while

15 $\mathcal{P}^{c}\leftarrow\mathcal{P}^{c}\cup(\mathcal{P}^{a}\cup p^{*})$;

16

17 end for

18$p^{*}\leftarrow\emptyset$;

19 while  _$\mathcal{C}(\mathcal{P}^{c})+\mathcal{C}(p^{*})\leq\mathcal{B}$
and $\bar{|\mathcal{P}|}\neq\emptyset$ _ do

20

21 $b\leftarrow\underset{s\in\bar{\mathcal{P}}}{argmax}\
\mathcal{I}((\mathcal{P}^{a}\cup\\{p^{*}\\})\cup\\{s\\})$;

22

23 if  _ $\mathcal{C}(\mathcal{P}^{c}\cup
p^{*})+\mathcal{C}(b)\leq\mathcal{B}$_ then

24 $p^{*}\leftarrow p^{*}\cup\\{b\\}$;

25 $\mathcal{B}\leftarrow\mathcal{B}-\mathcal{C}(b)$;

26

27 end if

28 $\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\\{b\\}$;

29

30 end while

31$\mathcal{P}^{c}\leftarrow\mathcal{P}^{c}\cup p^{*}$,
$\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\mathcal{P}^{c}$;

32 $b^{extra}\leftarrow\underset{s\in\bar{\mathcal{P}}}{argmax}\
\mathcal{I}(\mathcal{P}^{c}\cup\\{s\\})$;

33 $L^{a}\leftarrow\mathcal{I}(\mathcal{P}^{c})$,
$\mathcal{U}^{a}\leftarrow\mathcal{I}(\mathcal{P}^{c})+[\mathcal{B}-\mathcal{C}(\mathcal{P}^{c})].\frac{\mathcal{I}(\mathcal{P}^{c}\cup~{}b^{extra})-\mathcal{I}(\mathcal{P}^{c})}{\mathcal{C}(b^{extra})}$;

return $\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a}$

Algorithm 3 FastBoundEstimation

#### Complexity Analysis.

Initialization at Line No. $1$ will take $\mathcal{O}(1)$ time to execute. The
for loop at Line No. $2$ will execute for $\mathcal{O}(\ell)$ time and while
loop at line No. $3$ will execute for $\mathcal{O}(m)$ time and in Line No.
$4$, computing marginal gain will take $\mathcal{O}(\ell\cdot m^{2}\cdot t)$
time in which $t$ is the number of tuples in the trajectory database. Line No.
$5$ to $11$ will execute for $\mathcal{O}(m\cdot\ell)$ time. Hence, Line No.
$1$ to $12$ will take total $\mathcal{O}(\ell\cdot m^{2}\cdot t+m\cdot\ell)$
time to execute. Similarly, Line No. $13$ to $22$ will take
$\mathcal{O}(\ell\cdot m^{2}\cdot t+m\cdot\ell)$ time in the worst case. In-
Line No. $23$, calculating $b^{extra}$ will take $\mathcal{O}(m\cdot t)$ and
Line No. $24$ will take $\mathcal{O}(4\cdot m\cdot t)$ time. Hence, Algorithm
3 will take $\mathcal{O}(\ell\cdot m^{2}\cdot t+m\cdot\ell+m\cdot t)$ i.e.,
$\mathcal{O}(\ell\cdot m^{2}\cdot t)$ time in the worst case. The additional
space requirements for Algorithm 3 will be $\mathcal{O}(m+\ell)$.

###  3.4 Bound Estimation.

The branch and bound approach invokes Algorithm 4 for bound estimation in each
iteration. From Algorithm 1, we observed that selecting billboard slots using
greedy takes huge computational time to calculate the marginal gain and find
the slots having the maximum gain. Although the branch and bound with
Algorithm 3 gives a solution based on the highest influence value in each
iteration, it is not optimal. However, it reduces computational costs hugely.
Motivated by this, we propose a bound estimation approach in Algorithm 4
without traversing all the slots to estimate the bound with an approximation
of $\frac{\theta}{2}(1-1/e-\epsilon)$, where $\epsilon$ is a user-defined
parameter which balances the trade-off between accuracy and efficiency. Also,
we set a threshold $\tau$ in Line No. $2$ by calculating maximal of
$(\mathcal{I}(\mathcal{P}^{a}\cup\\{b\\})-\mathcal{I}(\mathcal{P}^{a}))/\mathcal{C}(b)$
and we progressively decrease the value of $\tau$ by a factor of $(1+e)$ and
insert an element into $p^{*}$. Here, one thing needs to be observed:
Algorithm 4 does not explore all the billboard slots to find the best
solution, and when the value of $\tau$ is small enough, the algorithm
terminates.

Data: $\mathcal{D}$, $\mathbb{BS}$, $I()$, $z_{j}$, $\mathcal{B}$,
$\mathcal{P}^{a}$, $\bar{\mathcal{P}}$, $\mathcal{Y}$.

Result: ($\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a}$)

1

$p^{*}\leftarrow\emptyset$, $\mathcal{P}^{c}\leftarrow\emptyset$,
$\epsilon\leftarrow 0.1$;

2 $\tau\leftarrow\underset{b\in\bar{\mathcal{P}}}{max}\
\frac{\mathcal{I}(\mathcal{P}^{a}\cup\\{b\\})-\mathcal{I}(\mathcal{P}^{a})}{\mathcal{C}(b)}$,
$\mathcal{B}^{r}\leftarrow\mathcal{B}-\mathcal{C}(\mathcal{P}^{a})$;

3 for  _each $z_{j}\in a_{z}$_ do

4 while  _$\mathcal{C}(\mathcal{P}^{a})+\mathcal{C}(p^{*})\leq\mathcal{B}$ and
$\mathcal{I}(\mathcal{P}^{a}\cup\\{p^{*}\\})\leq\sigma_{z_{j}}$ and
$\bar{|\mathcal{P}|}\neq\emptyset$ _ do

5 for  _$b\in\bar{\mathcal{P}}$_ do

6 if  _$\mathcal{C}(\mathcal{P}^{a}\cup p^{*})+\mathcal{C}(b)\leq\mathcal{B}$_
then

7 m =
$\mathcal{I}(\mathcal{P}^{a}\cup\\{b\\}|\mathcal{P}^{a})-\mathcal{I}(p^{*}|\mathcal{P}^{a})$;

8 if  _$\frac{m}{\mathcal{C}(b)}\geq\tau$_ then

9 $\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\\{b\\}$;

10 $p^{*}\leftarrow p^{*}\cup\\{b\\}$;

11

12 end if

13 if  _$\frac{m}{\mathcal{C}(b)} <\tau$_ then

14 break;

15

16 end if

17

18 end if

19

20 end for

21 $\tau\leftarrow\frac{\tau}{1+\epsilon}$;

22 if
_$\tau\leq\frac{\mathcal{I}(p^{*}|\mathcal{P}^{a})}{\mathcal{B}^{r}}\cdot\frac{e^{-1}}{1-e^{-1}}$_
then

23 break;

24

25 end if

26

27 end while

28 $\mathcal{P}^{c}\leftarrow\mathcal{P}^{c}\cup(\mathcal{P}^{a}\cup p^{*})$;

29

30 end for

31$p^{*}\leftarrow\emptyset$,
$\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\mathcal{P}^{c}$,
$\mathcal{B}\leftarrow\mathcal{B}-\mathcal{C}(\mathcal{P}^{c})$;

32

33while  _$\mathcal{C}(\mathcal{P}^{c})+\mathcal{C}(p^{*})\leq\mathcal{B}$ and
$\bar{|\mathcal{P}|}\neq\emptyset$ _ do

34 for  _$b\in\bar{\mathcal{P}}$_ do

35 if  _$\mathcal{C}(\mathcal{P}^{c}\cup
p^{*})+\mathcal{C}(b)\leq\mathcal{B}$_ then

36 m =
$\mathcal{I}(\mathcal{P}^{c}\cup\\{b\\}|\mathcal{P}^{c})-\mathcal{I}(p^{*}|\mathcal{P}^{c})$;

37 if  _$\frac{m}{\mathcal{C}(b)}\geq\tau$_ then

38 $\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\\{b\\}$;

39 $p^{*}\leftarrow p^{*}\cup\\{b\\}$;

40

41 end if

42 if  _$\frac{m}{\mathcal{C}(b)} <\tau$_ then

43 break;

44

45 end if

46

47 end if

48

49 end for

50 $\tau\leftarrow\frac{\tau}{1+\epsilon}$;

51 if
_$\tau\leq\frac{\mathcal{I}(p^{*}|\mathcal{P}^{a})}{\mathcal{B}^{r}}\cdot\frac{e^{-1}}{1-e^{-1}}$_
then

52 break;

53

54 end if

55

56 end while

57$\mathcal{P}^{c}\leftarrow\mathcal{P}^{c}\cup p^{*}$,
$\bar{\mathcal{P}}\leftarrow\bar{\mathcal{P}}\setminus\mathcal{P}^{c}$;

58 $b^{extra}\leftarrow\underset{s\in\bar{\mathcal{P}}}{argmax}\
\frac{\mathcal{I}(\mathcal{P}^{c}\cup\\{s\\})-\mathcal{I}(\mathcal{P}^{c})}{\mathcal{C}(\\{s\\})}$;

59 $L^{a}\leftarrow\mathcal{I}(\mathcal{P}^{c})$,
$\mathcal{U}^{a}\leftarrow\mathcal{I}(\mathcal{P}^{c})+[\mathcal{B}-\mathcal{C}(\mathcal{P}^{c})].\frac{\mathcal{I}(\mathcal{P}^{c}\cup~{}b^{extra})-\mathcal{I}(\mathcal{P}^{c})}{\mathcal{C}(b^{extra})}$;

return $\mathcal{P}^{c},L^{a},\mathcal{Y},\mathcal{U}^{a}$

Algorithm 4 BoundEstimation

#### Complexity Analysis.

Initialization at Line No. $1$ and calculating $\tau$ at Line No. $2$ will
take $\mathcal{O}(1)$ and $\mathcal{O}(2\cdot m\cdot t)$ time, respectively.
Line No. $3$ for loop and Line No. $4$ while loop will execute for
$\mathcal{O}(\ell)$ and $\mathcal{O}(m)$ time, respectively. Line No. $5$ for
loop will execute for $\mathcal{O}(m^{2}\cdot\ell)$ and Line No. $7$ will take
$\mathcal{O}(2\cdot m^{2}\cdot\ell\cdot t)$ time to execute. Line No. $8$ to
$16$ will execute for $\mathcal{O}(m^{2}\cdot\ell)$ and Line No. $17$ will
execute for $\mathcal{O}(m\cdot\ell)$. Finally, in Line No. $18$ to $20$ will
take $\mathcal{O}(m\cdot\ell\cdot t)$ time. Hence, Line No. $1$ to $23$ will
take $\mathcal{O}(2\cdot m\cdot t+2\cdot m^{2}\cdot\ell\cdot
t+m^{2}\cdot\ell+m\cdot\ell+m\cdot\ell\cdot t)$ i.e., $\mathcal{O}(2\cdot
m^{2}\cdot\ell\cdot t)$ time to execute. Similarly, Line No. $24$ to $43$ will
take $\mathcal{O}(2\cdot m^{2}\cdot\ell\cdot t)$ time to execute. In-Line No.
$44$ will take $\mathcal{O}(m\cdot t)$ and Line No. $45$ will take
$\mathcal{O}(4\cdot m\cdot t)$ time to execute. Hence, Algorithm 4 will take
$\mathcal{O}(2\cdot m^{2}\cdot\ell\cdot t+2\cdot m^{2}\cdot\ell\cdot t+2\cdot
m\cdot t+4\cdot m\cdot t)$ i.e., $\mathcal{O}(m^{2}\cdot\ell\cdot t)$ time in
the worst case to execute. The additional space requirements for Algorithm 4
will be $\mathcal{O}(m+\ell)$.

#### Theoretical analysis related to performance.

Due to space limitations, we have not conducted an elaborate analysis of our
proposed methods. In our case, we have used the results from the study by
Zhang et al. [10] and state their result in Theorem 3.1.

###### Theorem 3.1

The branch and bound approach invoking Algorithm 4 and it results an optimal
solution set $(\mathcal{OPT})$ from the billboard slots set
$\bar{\mathcal{P}}$ then it follows the following criteria :

$\mathcal{I}(\bar{\mathcal{P}})\geq\frac{\theta}{2}(1-1/e-\epsilon)\cdot\mathcal{I}(\mathcal{OPT}).$
(2)

#### An Illustrative Example.

Consider an influence provider has four billboard slots
$\mathcal{BS}=\\{b_{1},b_{2},b_{3},b_{4}\\}$ and an advertiser $a_{1}$
approaches to the influence provider with required influence demand from two
different zones $z_{1}$ and $z_{2}$ for budget $\mathcal{B}$. It can be
denoted in the form of vector $[(\sigma_{z_{1}},\sigma_{z_{2}}),\mathcal{B}]$.
Now, among these four slots $b_{1}$ and $b_{2}$ belongs to zone $z_{1}$ with
influence value $2$ and $3$ respectively, $b_{3}$ belongs to zone $z_{2}$ with
influence value $7$ and $b_{4}$ belongs to zone $z_{3}$ with influence value
$5$ as shown in Table 2. Next, the working of Branch and Bound framework in
Algorithm 2 is as follows: At first, we initialize the max heap $\mathcal{H}$
with an entry $(\\{\\},\\{b_{1},b_{2},b_{3},b_{4}\\},[(5,7),1000])$. The set
$\mathcal{P}$ is empty, and the set $\bar{\mathcal{P}}$ contains all the
billboard slots $\\{b_{1},b_{2},b_{3},b_{4}\\}$ in the top part of the search
tree as shown in the Figure 2. In the search tree, every node has an entry
like $(\mathcal{P},\bar{\mathcal{P}},\mathcal{U})$ and in each step the values
of $\mathcal{P}$, $\bar{\mathcal{P}}$, and $\mathcal{U}$ are updated. Next, in
step $1$, we pop the initial heap entry and, based on the budget and zonal
constraint, push a new branch into the heap, i.e.,
$(\\{b_{1}\\},\\{b_{2},b_{3},b_{4}\\},[(3,7),900])$ by invoking Algorithm 3 or
4. Since the $L^{a}>L_{G}$, we update the value of $\hat{\mathcal{P}}$ with
$\mathcal{P}^{c}$. Similarly, at steps $2,3,4$, the newly generated branches
are pushed into the heap. However, in step $4,7,10,13,15,17$, adding billboard
slot $b_{4}$ does not satisfy the zonal influence constraint, and these
entries are not inserted into the heap. Next, in step $14$, the zonal
influence demand is satisfied, but some budget remains. So, this budget is
utilized by taking slots from available zones, i.e., $b_{4}$ is added to the
solution set, and the budget is exhausted. From Figure 2, it is clear that the
path ($step~{}1\rightarrow~{}step~{}5\rightarrow step~{}14\rightarrow
step~{}18$) gives an optimal solution that satisfies all the constraints and
when $L_{G}\geq U_{G}$ Algorithm 2 terminates.

$\mathcal{BS}_{i}$ | $bs_{1}$ | $bs_{2}$ | $bs_{3}$ | $bs_{4}$
---|---|---|---|---
$I(bs_{i})$ | 2 | 3 | 7 | 5
$C(bs_{i})$ | 100 | 200 | 400 | 300
Zone Info. | $z_{1}$ | $z_{1}$ | $z_{2}$ | $z_{3}$
Figure 1:  Billboard Info.

Figure 2: A running example

##  4 Experimental Evaluation

This section discusses the experimental evaluation to show the effectiveness
of the proposed solution methodologies. Initially, we start by describing the
datasets.

#### Dataset Descriptions.

We conduct experiments on real-world trajectory check-in datasets for New York
City (NYC) and Los Angeles (LA). The
NYC444https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page dataset
contains $227,428$ check-ins between April 12, 2012, and February 16, 2013,
and The LA555https://github.com/Ibtihal-Alablani dataset contains $74,170$
check-in from $15$ different streets of Los Angles. We have crawled billboard
datasets from the different locations of New York City and Los Angeles from
LAMAR666http://www..lamar.com/InventoryBrowser, one of the largest billboard
providers worldwide. The NYC billboard dataset consists of $1031040$ slots and
the LA dataset consists of $2135520$ slots. However, in our experiment, we
used $1500$ and $2500$ slots for NYC and LA, respectively. Additionally, we
divide the billboard datasets based on latitude and longitude for New York
City and Los Angeles into $5$ and $3$ different geographic zones,
respectively.

###  4.1 Experimental Setup.

The following experimental setups are considered in our experiments.

#### Key Parameters.

All the key parameters are summarized in Table 1, and the default parameters
are highlighted in bold. In our experiments, we vary only one parameter and
keep the rest of the parameters in the default setting. In Algorithm 2,
$\theta$ controls the termination condition while $\epsilon$ is used to make
trade efficiency with accuracy. The distance threshold $\eta$ denotes the
maximum distance in which a billboard can influence the maximum number of
trajectories.

Table 1:  Key Parameters Parameter |  Values
---|---
$\mathcal{B}$ |  $5k,10k,15k,20k,25k$
$\epsilon$ |  $10^{-4},10^{-3},10^{-2},10^{-1},1$
$\theta$ |  $0.5,0.6,\textbf{0.7},0.8,0.9$
$\eta$ |  $25m,50m,\textbf{100m},125m,150m$

#### Environment Setup.

All Python codes were executed on an HP Z4 workstation equipped with 64 GB of
memory and an Xeon(R) 3.50 GHz processor.

#### Billboard cost.

An advertising company like LAMAR does not provide an exact cost of billboard
slots. As reported in the existing studies [7, 8, 10], a billboard’s cost is
proportional to its corresponding influence value. Hence, we have calculated
using the following setting:
$\mathcal{C}(b)=\lfloor\delta*\mathcal{I}(b)/10\rfloor$, where $\delta$ is a
factor randomly chosen between $0.8$ to $1.1$ to simulate the cost
fluctuation.

#### Performance Measurement.

Each baseline and the proposed method are evaluated for their influence and
runtime, and each experiment is repeated five times to demonstrate the
effectiveness and efficiency of the proposed methods. Average results from
these experiments are reported.

###  4.2 Algorithms Compared.

In this paper, our goal is to evaluate the effectiveness and efficiency of the
proposed methods. Hence, we compare our methods with the following baselines:

#### Top-$k$.

Each iteration selects a billboard slot, which influences a maximum number of
trajectories until the zone-specific influence demand and budget constraints
are satisfied.

####  Random.

This is the simple approach where it will choose billboard slots uniformly at
random in each iteration until the zonal influence and budget constraints are
satisfied.

###  4.3 Goals of the Experiments.

In this study, we want to address the following Research Questions (RQ).

  * •

RQ1: How do the influence value and runtime change if we increase the budget
to select billboard slots?

  * •

RQ2: For the Branch and Bound algorithm, varying values of $\theta$ and
$\epsilon$, how do the runtime and the influence quality change?

  * •

RQ3: How do the influence value and run-time change if the number of demanding
zones increases by the advertisers?

  * •

RQ4: How do the influence and run-time change if we vary trajectory size?

###  4.4 Experimental Results.

This section will discuss experimental results for the proposed and existing
solution methodologies. Due to space limitations, we cannot include different
varying parameter results, which will come in the journal version of this
work.

#### Budget Vs. Influence.

Figure 3(a) and 3(c) show the effectiveness of the proposed as well as
baseline methodologies in the NYC and LA datasets. From this, we have
significant observations. First, when the budget increases from $5k$ to $25k$
in NYC and $50k$ to $150k$ in the LA dataset, the BBS outperforms the BFBS and
the greedy approach by $26\%$ to $28\%$ and $20\%$ to $27\%$ respectively.
Second, the BFBS has worse performance, as it gives preference to the slots
with the highest influence value in each iteration, which are the most
expensive in the real world. So, it can choose only a limited number of slots
when the budget is less, and due to the influence overlap, the BBS performs
well compared to the BFBS approach. Third, the impact of the BBS and the BFBS
is greater in NYC than in the LA dataset, and the possible reason is the
distribution of trajectory in the trajectory dataset, i.e., the influence
overlap is less in the NYC Dataset.

|  |
---|---|---
(a) Influence in NYC | (b) Runtime in NYC | (c) Influence in LA
|  |
(d) Runtime in LA | (e) $\theta$ Vs. Influence (NYC) | (f) $\theta$ Vs. Time (NYC)
|  |
(g) Scalability Test (NYC) | (h) $\epsilon$ Vs. Influence (NYC) | (i) $\epsilon$ Vs. Time (NYC)
Figure 3: Varying Budget in NYC (a,b), LA (c,d), Varying $\theta$ in NYC
(e,f), Varying No. of Slot in NYC (g), Varying $\epsilon$ in NYC (h,i)

#### Budget Vs. Time.

From Figure 3(b) and 3(d), we have three observations. First, the running time
of BFBS is very low compared to the BBS and Greedy approach because in BFBS,
for every branch, the slots are selected based on the highest individual
influence value, whereas in Greedy, slots are selected based on marginal gain
computation. However, for every branch, the BBS method compute marginal gain
for each slot in each iteration, which resulted in a significant increase in
run time. Second, with the increased budget, the computational cost of each
proposed and baseline method increases. Third, Top-$k$ and Random is the
fastest approach because they scan all billboard slots only once.

#### Varying $\epsilon,\theta$.

The user-defined parameter $\theta$ controls the termination criteria in
Algorithm 2. The larger $\theta$ value will increase the effectiveness with
worse efficiency. Figure 3(c), 3(d) shows the effect of varying $\theta$ in
the NYC dataset. Next, when the $\epsilon$ value increases from $0.0001$ to
$1$, the effectiveness of the BFBS and BBS decreases by at least $5\%$ to
$10\%$.However, the efficiency increases by $20\%$ to $30\%$. We found that
the effectiveness and efficiency are stable when $\theta$ and $\epsilon$
values are $0.7$ and $0.1$, respectively, and chose this as the default
setting.

#### Scalability Test.

Figure 3(g) shows that in the NYC dataset, efficiency is very sensitive in BBS
compared to the BFBS when we vary the billboard slot size from $300$ to
$1500$. It is observed that the run-time increase rate in BBS compared to
Greedy and BFBS is almost $57\%$ to $86\%$ and $92\%$ to $95\%$, respectively.

#### Additional Discussion.

Now, we discuss the impact of additional parameters, e.g., varying distance
$(\eta)$, no. of zones $(|\ell|)$, size of the trajectory $(|\mathcal{T}|)$,
etc. First, the influence of all the proposed and baseline methods increases
with the distance increase. This happens because each billboard slot can
influence a large number of trajectories. Second, when zone-specific influence
demand rises with the fixed budget, the computational cost of BBS and BFBS
decreases. This happens because most of the budget is used to select slots for
demanding zones, and very little is used to choose slots from the remaining
slots in any of the zones. Third, in the case of the NYC dataset varying
trajectory size from $40k$ to $120k$, the computational time increases
drastically in BBS compared to the BFBS and Greedy approach. The BBS and
Greedy outperform the BFBS and baseline methods by up to $40\%$ to $60\%$ in
terms of influence with the increase in trajectory size.

##  5 Conclusion and Future Research Direction

In this paper, we study the problem of influential billboard slot selection
under zonal influence constraint and formulate this as a discrete optimization
problem. We propose a simple greedy and branch and bound approach with two
bound estimation techniques to address this problem. We experimented with two
real-world billboards and trajectory datasets and analyzed their time and
space requirements. We also analyzed proposed methods to obtain the
performance guarantee. Our proposed BBS gives an optimal solution; however,
its computational time requirements are its bottleneck. Therefore, our future
work on this problem is to develop more efficient solution methodologies.

## References

  * [1] Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using pruned submodularity graph. In: Chen, W., Yao, L., Cai, T., Pan, S., Shen, T., Li, X. (eds.) Advanced Data Mining and Applications. pp. 216–230. (2022)
  * [2] Ali, D., Banerjee, S., Prasad, Y.: Influential billboard slot selection using spatial clustering and pruned submodularity graph. arXiv preprint arXiv:2305.08949 (2023)
  * [3] Ali, D., Banerjee, S., Prasad, Y.: Minimizing regret in billboard advertisement under zonal influence constraint. arXiv preprint arXiv:2402.01294 (2024)
  * [4] Ali, D., Bhagat, A.K., Banerjee, S., Prasad, Y.: Efficient algorithms for regret minimization in billboard advertisement (student abstract). Proceedings of the AAAI Conference on Artificial Intelligence 37(13), 16148–16149 (Sep 2023)
  * [5] Wang, L., Yu, Z., Guo, B., Yang, D., Ma, L., Liu, Z., Xiong, F.: Data-driven targeted advertising recommendation system for outdoor billboard. ACM Transactions on Intelligent Systems and Technology (TIST) 13(2), 1–23 (2022)
  * [6] Wang, L., Yu, Z., Yang, D., Ma, H., Sheng, H.: Efficiently targeted billboard advertising using crowdsensing vehicle trajectory data. IEEE Transactions on Industrial Informatics 16(2), 1058–1066 (2020)
  * [7] Zahrádka, J., Machová, V., Kučera, J.: What is the price of outdoor advertising: A case study of the czech republic? Ad Alta: Journal of Interdisciplinary Research (2021)
  * [8] Zhang, P., Bao, Z., Li, Y., Li, G., Zhang, Y., Peng, Z.: Trajectory-driven influential billboard placement. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. p. 2748–2757. KDD ’18, Association for Computing Machinery, New York, NY, USA (2018)
  * [9] Zhang, P., Bao, Z., Li, Y., Li, G., Zhang, Y., Peng, Z.: Towards an optimal outdoor advertising placement: When a budget constraint meets moving trajectories. ACM Transactions on Knowledge Discovery from Data (TKDD) 14(5), 1–32 (2020)
  * [10] Zhang, Y., Li, Y., Bao, Z., Mo, S., Zhang, P.: Optimizing impression counts for outdoor advertising. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. p. 1205–1215. KDD ’19, Association for Computing Machinery, New York, NY, USA (2019)
  * [11] Zhang, Y., Li, Y., Bao, Z., Zheng, B., Jagadish, H.V.: Minimizing the regret of an influence provider. In: Proceedings of the 2021 International Conference on Management of Data. p. 2115–2127. SIGMOD ’21, Association for Computing Machinery, New York, NY, USA (2021)