Maximizing the Utility in Location-Based Mobile Advertising

Peng Cheng, Xiang Lian, Lei Chen, Siyuan Liu

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


With the rapid development of mobile technology, nowadays, people spend a large amount of time on mobile devices. The locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisements. In this paper, we consider an important location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the {sf reconciliation approach}reconciliationapproach, which has an approximation ratio of (1-epsilon)cdot theta(1-ϵ)·θ. In addition, we also address the online scenario, in which customers arrive in a streaming fashion, with one novel online algorithm, namely the {sf online adaptive factor-aware approach}onlineadaptivefactor-awareapproach, which has a competitive ratio (compared to the optimal solution of the offline scenario) of frac{ln (g)+1}{theta }ln(g)+1θ, g>eg>e, where ee is the base of the natural logarithm. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

Original languageEnglish (US)
Pages (from-to)776-788
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number2
StatePublished - Feb 1 2022

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Maximizing the Utility in Location-Based Mobile Advertising'. Together they form a unique fingerprint.

Cite this