  The selection of influential billboard slots remains an important problem in
billboard advertisements. Existing studies on this problem have not considered
the case of context-specific influence probability. To bridge this gap, in this
paper, we introduce the Context Dependent Influential Billboard Slot Selection
Problem. First, we show that the problem is NP-hard. We also show that the
influence function holds the bi-monotonicity, bi-submodularity, and
non-negativity properties. We propose an orthant-wise Stochastic Greedy
approach to solve this problem. We show that this method leads to a constant
factor approximation guarantee. Subsequently, we propose an orthant-wise
Incremental and Lazy Greedy approach. In a generic sense, this is a method for
maximizing a bi-submodular function under the cardinality constraint, which may
also be of independent interest. We analyze the performance guarantee of this
algorithm as well as time and space complexity. The proposed solution
approaches have been implemented with real-world billboard and trajectory
datasets. We compare the performance of our method with many baseline methods,
and the results are reported. Our proposed orthant-wise stochastic greedy
approach leads to significant results when the parameters are set properly with
reasonable computational overhead.
