Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints

Abstract

Owing to the accuracy and flexibility, mobile advertising has become a very attractive marketing method based on smart mobile terminals. The more common mobile advertisement distribution methods are based on location and content. But most of them donart take into account the limited duration time of mobile users and the timeliness of advertising, which makes mobile advertisement distribution suffer from low propagation efficiency. To make up for this deficiency, we propose the advertisement platformars expected income maximization problem (EIMP), and prove its NP-hardness. As far as we know, EIMP is a combination of the 0–1 multi-dimensional and multiple knapsack problem, which is even harder. In dealing with this difficulty, we fortunately find that this problem could be transformed into a maximizing monotone submodular set function, which is subject to partition matroid constraints. Then we propose a simple but effective greedy algorithm TIMAO (Time-sensitive Mobile Advertisement Offloading) which has a constant approximation ratio of 1/3 to provide a performance guarantee for this issue. Finally, extensive evaluations are conducted. The results show that compared with the random selection method, TIMAO increases the expected income of the platform by about two times. And it achieves 99.2% of the near optimal results obtained by the CPLEX tool-box. Moreover, we propose an important metric, the duty cycle, to evaluate system performance in time domain. The results show that our scheme could increase the time duty cycle by about average 10% compared with the random selection.

Keywords

• Mobile advertisement offloading
• time sensitivity
• budget constraint
• submodular function
• partition matroid constraints