  Advertisement disseminations based on Roadside Access Points (RAPs) in
vehicular ad-hoc networks (VANETs) attract lots of attentions and have a
promising prospect. In this paper, we focus on a roadside advertisement
dissemination, including three basic elements: RAP Service Provider (RSP),
mobile vehicles and shops. The RSP has deployed many RAPs at different
locations in a city. A shop wants to rent some RAPs, which can disseminate
advertisements to vehicles with some probabilites. Then, it tries to select the
minimal number of RAPs to finish the advertisement dissemination, in order to
save the expenses. Meanwhile, the selected RAPs need to ensure that each
vehicle's probability of receiving advertisement successfully is not less than
a threshold. We prove that this RAP selection problem is NP-hard. In order to
solve this problem, we propose a greedy approximation algorithm, and give the
corresponding approximation ratio. Further, we conduct extensive simulations on
real world data sets to prove the good performance of this algorithm.
