Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8794835/ |
| _version_ | 1811212121765052416 |
|---|---|
| author | Wanru Xu Chaocan Xiang Chang Tian |
| author_facet | Wanru Xu Chaocan Xiang Chang Tian |
| author_sort | Wanru Xu |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T05:23:28Z |
| format | Article |
| id | doaj.art-5f3d72f0dd604511813065c755c25e05 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T05:23:28Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-5f3d72f0dd604511813065c755c25e052022-12-22T03:46:22ZengIEEEIEEE Access2169-35362019-01-01711524911526010.1109/ACCESS.2019.29348258794835Near Optimal Dynamic Mobile Advertisement Offloading With Time ConstraintsWanru Xu0https://orcid.org/0000-0003-0235-6978Chaocan Xiang1Chang Tian2Graduate School, Army Engineering University of PLA, Nanjing, ChinaCollege of Computer Science, Chongqing University, Chongqing, ChinaCollege of Communication Engineering, Army Engineering University of PLA, Nanjing, ChinaOwing 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.https://ieeexplore.ieee.org/document/8794835/Mobile advertisement offloadingtime sensitivitybudget constraintsubmodular functionpartition matroid constraints |
| spellingShingle | Wanru Xu Chaocan Xiang Chang Tian Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints IEEE Access Mobile advertisement offloading time sensitivity budget constraint submodular function partition matroid constraints |
| title | Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints |
| title_full | Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints |
| title_fullStr | Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints |
| title_full_unstemmed | Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints |
| title_short | Near Optimal Dynamic Mobile Advertisement Offloading With Time Constraints |
| title_sort | near optimal dynamic mobile advertisement offloading with time constraints |
| topic | Mobile advertisement offloading time sensitivity budget constraint submodular function partition matroid constraints |
| url | https://ieeexplore.ieee.org/document/8794835/ |
| work_keys_str_mv | AT wanruxu nearoptimaldynamicmobileadvertisementoffloadingwithtimeconstraints AT chaocanxiang nearoptimaldynamicmobileadvertisementoffloadingwithtimeconstraints AT changtian nearoptimaldynamicmobileadvertisementoffloadingwithtimeconstraints |