Ad network optimization: Evaluating linear relaxations

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

Resultado de la investigación: Contribución a una conferenciaArtículo de conferencia

1 Cita (Scopus)

Resumen

This paper presents a theoretical and empirical analysis of linear programming relaxations to ad network optimization. The underlying problem is to select a sequence of ads to send to websites, while an optimal policy can be produced using a Markov Decision Process, in practice one must resort to relaxations to bypass the curse of dimensionality. We focus on a state-of-art relaxation scheme based on linear programming. We build a Markov Decision Process that captures the worst-case behavior of such a linear programming relaxation, and derive theoretical guarantees concerning linear relaxations. We then report on extensive empirical evaluation of linear relaxations, our results suggest that for large problems (similar to ones found in practice), the loss of performance introduced by linear relaxations is rather small. © 2013 IEEE.
Idioma originalInglés estadounidense
Páginas219-224
Número de páginas6
DOI
EstadoPublicada - 1 ene 2013
Publicado de forma externa
EventoProceedings - 2013 Brazilian Conference on Intelligent Systems, BRACIS 2013 -
Duración: 1 ene 2013 → …

Conferencia

ConferenciaProceedings - 2013 Brazilian Conference on Intelligent Systems, BRACIS 2013
Período1/01/13 → …

Huella Profundice en los temas de investigación de 'Ad network optimization: Evaluating linear relaxations'. En conjunto forman una huella única.

  • Citar esto

    Truzzi, F. S., Da Silva, V. F., Costa, A. H. R., & Cozman, F. G. (2013). Ad network optimization: Evaluating linear relaxations. 219-224. Papel presentado en Proceedings - 2013 Brazilian Conference on Intelligent Systems, BRACIS 2013, . https://doi.org/10.1109/BRACIS.2013.44