Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/BRACIS.2013.44 | BRACIS |
Keywords | Field | DocType |
Markov processes,advertising,linear programming,Markov decision process,Web sites,ad network optimization,ads sequence,curse-of-dimensionality,linear programming relaxations,linear relaxations evaluation,state-of-art relaxation scheme,Ad Network,Linear Programming,Markov Decision Process | Linear-fractional programming,Mathematical optimization,Markov process,Markov model,Partially observable Markov decision process,Markov decision process,Randomized rounding,Linear programming,Linear programming relaxation,Mathematics | Conference |
Citations | PageRank | References |
1 | 0.39 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Flávio Sales Truzzi | 1 | 3 | 1.10 |
| Valdinei Freire da Silva | 2 | 25 | 6.86 |
| Anna Helena Reali Costa | 3 | 192 | 31.97 |
| Fabio G. Cozman | 4 | 1200 | 172.21 |