TIMAO: Time-Sensitive Mobile Advertisement Offloading with Performance Guarantee

摘要

Mobile advertising has played an important role with the prevalence of smart mobile devices. Most of the previous studies focus on location-based or content-based mobile advertisement propagation and distribution, which are suffered by the low propagation efficiency, because advertisements could not be available to mobile users within limited time span. Conventional offloading schemes could perfectly distribute advertisements according to user's interest, but have not fully respected the time sensitivity in mobile advertisement distribution. In response to this stalemate, we introduce the advertisement platform's expected income maximization problem (EIMP), and prove its NP-hardness. To our knowledge, ours is even harder than conventional 0-1 mutlidimensional and multiple knapsack problem. But inspiringly we find that it could be transformed into a maximizing monotone submodular set function, being subjected to partition matroid constraints. Then a simple but effective greedy algorithm (TIMAO, time-sensitive mobile advertisement offloading)is proposed to solve the EIMP with approximation ratio of 1/3. Finally, the evaluation results show that TIMAO could double the platform's expected income comparing with the random selection method and reach 99.2% of the near optimal values achieved by CPLEX tool-box. At the same time, it increases the time duty cycle by about average 10% compared with the random selection.