Evaluation of linear relaxations in Ad Network optimization for online marketing

Valdinei Freire, Flávio Sales Truzzi, Anna Helena Reali Costa, Fabio Gagliardi Cozman

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

2 Citas (Scopus)


© 2015, Freire et al. Background: Ad Networks connect advertisers to websites that want to host advertisements. When users request websites, the Ad Network decides which ad to send so as to maximize the number of ads that are clicked by users. Due to the difficulty in solving such maximization problems, there are solutions in the literature that are based on linear programming (LP) relaxations. Methods: We contribute with a formulation for the Ad Network optimization problem, where it is cast as a Markov decision process (MDP). We analyze theoretically the relative performance of MDP and LP solutions. We report on an empirical evaluation of solutions for LP relaxations, in which we analyze the effect of problem size in performance loss compared to the MDP solution. Results: We show that in some configurations, the LP relaxations incur in approximately 58 % revenue loss when compared to MDP solutions. However, such relative loss decreases as problem size increases. We also propose new heuristics to improve the use of solutions achieved by LP relaxation. Conclusions: We show that solutions obtained by LP relaxations are suitable for Ad Networks, as the performance loss introduced by such solutions are small in large problems observed in practice.
Idioma originalInglés estadounidense
PublicaciónJournal of the Brazilian Computer Society
EstadoPublicada - 19 dic. 2015
Publicado de forma externa


Profundice en los temas de investigación de 'Evaluation of linear relaxations in Ad Network optimization for online marketing'. En conjunto forman una huella única.

Citar esto