  Creating and maximizing influence among the customers is one of the central
goals of an advertiser, and hence, remains an active area of research in recent
times. In this advertisement technique, the advertisers approach an influence
provider for a specific number of views of their content on a payment basis.
Now, if the influence provider can provide the required number of views or
more, he will receive the full, else a partial payment. In the context of an
influence provider, it is a loss for him if he offers more or less views. This
is formalized as 'Regret', and naturally, in the context of the influence
provider, the goal will be to minimize this quantity. In this paper, we solve
this problem in the context of billboard advertisement and pose it as a
discrete optimization problem. We propose four efficient solution approaches
for this problem and analyze them to understand their time and space
complexity. We implement all the solution methodologies with real-life datasets
and compare the obtained results with the existing solution approaches from the
literature. We observe that the proposed solutions lead to less regret while
taking less computational time.
