D-AdFeed: A diversity-aware utility-maximizing advertising framework for mobile users

摘要

With the advance of the ubiquity of GPS-equipped smartphones, mobile advertising has become more prevalent and location-aware. In mobile advertising systems, vendors have limited budget, and mobile users have limited capacity to receive ads. Existing systems simply send users the ads with largest utility scores. Unfortunately, the major limitation of this approach is that, the ads received by a particular user may belong to the same category (e.g., Chinese Food, Shopping Mall). We argue that diversity is a very important feature for location-based advertising, since it helps users discover new places and activities. In this paper, we propose D-AdFeed, a diversity-aware mobile advertising framework that maximizes the overall utility of assigning ads to each user under the constraints that the ads received by a particular user should belong to different categories. We formulate the problem as a generalized multi-constraint multi-choice knapsack problem. and propose a genetic approach as well as a greedy algorithm to solve it. Moreover, we consider the online scenario of the problem and propose a dynamic hybrid mutation genetic algorithm for it. Experimental results show that our proposed algorithms outperform the brute-force optimal algorithm by at least an order of magnitude in terms of the running time while the relative error of the utility score is acceptable. In general, D-AdFeed improves the utility, diversity and efficiency of recommending the ads to mobile users.