  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.
