ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Mobile user propagation capability evaluation and coverage optimization algorithm

  • School of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2017.07.004
  • Received Date: 28 August 2016
  • Rev Recd Date: 08 December 2016
  • Publish Date: 31 July 2017
    Abstract

  • Abstract

    The distribution efficiency of mobile advertising is extremely important for both advertisers and users. Few studies have been conducted on efficient ad delivery, especially user tracing and the budget. In order to obtain a feasible and effective mobile advertising distribution policy, the concept of location-centric mobile crowd sourcing network was presented to replace the traditional user-centric networks and platforms, in which the location information for advertizing distribution plays a crucial role. Therefore, the user selection under the interested area coverage(interested area coverage， IAC) region was mainly focused upon. However, research centering on location information we need requires the consideration of the temporal characteristics of each user， and effective calculation of the ICA. The problem will be more difficult to solve when considering the budget constraint. To address these challenges, considering the location sensitive mobile advertising applications, and a user selection solution was proposed， which was proved to be an NP-hard budget-constrained problem. Then, the submodularity problem was explored and a simple and effective heuristic was presented whose approximate ratio is(1－

    Abstract

    The distribution efficiency of mobile advertising is extremely important for both advertisers and users. Few studies have been conducted on efficient ad delivery, especially user tracing and the budget. In order to obtain a feasible and effective mobile advertising distribution policy, the concept of location-centric mobile crowd sourcing network was presented to replace the traditional user-centric networks and platforms, in which the location information for advertizing distribution plays a crucial role. Therefore, the user selection under the interested area coverage(interested area coverage， IAC) region was mainly focused upon. However, research centering on location information we need requires the consideration of the temporal characteristics of each user， and effective calculation of the ICA. The problem will be more difficult to solve when considering the budget constraint. To address these challenges, considering the location sensitive mobile advertising applications, and a user selection solution was proposed， which was proved to be an NP-hard budget-constrained problem. Then, the submodularity problem was explored and a simple and effective heuristic was presented whose approximate ratio is(1－
    • FullText(HTML)
  • loading
    • References(12)
  • [1]
    BORGS C, CHAYES J, IMMORLICA N, et al. Dynamics of bid optimization in online advertisement auctions[C]// Proceedings of the 16th International Conference on World Wide Web. Banff, Canada: ACM Press, 2007: 531-540.
    [2]
    MAHDIAN M, NAZERZADEH H, SABERI A. Allocating online advertisement space with unreliable estimates[C]// Proceedings of the 8th ACM Conference on Electronic Commerce. San Diego: ACM Press, 2007: 288-294.
    [3]
    KLMEL B, ALEXAKIS S. Location based target advertising[C]// Proceedings of the First International Conference on Mobile Business. Athens, Greece: Springer, 2002: 1-7.
    [4]
    BANERJEE S, DHOLAKIA R R. Mobile advertising: Does location based advertising work?[J]. International Journal of Mobile Marketing, 2008, 3(2): 68-74.
    [5]
    NATH S, LIN F X Z, RAVINDRANATH L, et al. SmartAds: Bringing contextual ads to mobile apps[C]// Proceeding of the 11th Annual International Conference on Mobile Systems, Applications, and Services. Taipei, China: ACM Press, 2013: 111-124.
    [6]
    NATH S. Madscope: Characterizing mobile in-app targeted ads[C]// Proceedings of the 13th Annual International Conference on Mobile Systems, Applications, and Services. Florence, Italy: ACM Press, 2015: 59-73.
    [7]
    KRAUSE A, GUESTRIN C. Near-optimal observation selection using submodular functions[C]// Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada: AAAI Press, 2007, 2: 1650-1654.
    [8]
    KEMPE D, KLEINBERG J, TARDOS . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM Press, 2003: 137-146.
    [9]
    KRAUSE A, GOLOVIN D. Submodular function maximization[M]// Tractability: Practical Approaches to Hard Problems. Cambridge: Cambridge University Press, 2014: 71-104.
    [10]
    KHULLER S, MOSS A, NAOR J S. The budgeted maximum coverage problem[J]. Information Processing Letters, 1999, 70(1): 39-45.
    [11]
    Kuo T W, Lin K C J, Tsai M J. Maximizing submodular set function with connectivity constraint: Theory and application to networks[J]. IEEE/ACM Transactions on Networking (TON), 2015, 23(2): 533-546.
    [12]
    Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I[J]. Mathematical Programming, 1978, 14(1): 265-294.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    BORGS C, CHAYES J, IMMORLICA N, et al. Dynamics of bid optimization in online advertisement auctions[C]// Proceedings of the 16th International Conference on World Wide Web. Banff, Canada: ACM Press, 2007: 531-540.
    [2]
    MAHDIAN M, NAZERZADEH H, SABERI A. Allocating online advertisement space with unreliable estimates[C]// Proceedings of the 8th ACM Conference on Electronic Commerce. San Diego: ACM Press, 2007: 288-294.
    [3]
    KLMEL B, ALEXAKIS S. Location based target advertising[C]// Proceedings of the First International Conference on Mobile Business. Athens, Greece: Springer, 2002: 1-7.
    [4]
    BANERJEE S, DHOLAKIA R R. Mobile advertising: Does location based advertising work?[J]. International Journal of Mobile Marketing, 2008, 3(2): 68-74.
    [5]
    NATH S, LIN F X Z, RAVINDRANATH L, et al. SmartAds: Bringing contextual ads to mobile apps[C]// Proceeding of the 11th Annual International Conference on Mobile Systems, Applications, and Services. Taipei, China: ACM Press, 2013: 111-124.
    [6]
    NATH S. Madscope: Characterizing mobile in-app targeted ads[C]// Proceedings of the 13th Annual International Conference on Mobile Systems, Applications, and Services. Florence, Italy: ACM Press, 2015: 59-73.
    [7]
    KRAUSE A, GUESTRIN C. Near-optimal observation selection using submodular functions[C]// Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada: AAAI Press, 2007, 2: 1650-1654.
    [8]
    KEMPE D, KLEINBERG J, TARDOS . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM Press, 2003: 137-146.
    [9]
    KRAUSE A, GOLOVIN D. Submodular function maximization[M]// Tractability: Practical Approaches to Hard Problems. Cambridge: Cambridge University Press, 2014: 71-104.
    [10]
    KHULLER S, MOSS A, NAOR J S. The budgeted maximum coverage problem[J]. Information Processing Letters, 1999, 70(1): 39-45.
    [11]
    Kuo T W, Lin K C J, Tsai M J. Maximizing submodular set function with connectivity constraint: Theory and application to networks[J]. IEEE/ACM Transactions on Networking (TON), 2015, 23(2): 533-546.
    [12]
    Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I[J]. Mathematical Programming, 1978, 14(1): 265-294.
    Recommended articles
    TrendMD
    Volume 47 Issue 7 page: 569-574
    Cover

    Article Metrics

    Article views (475) PDF downloads(237)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return