diff options
Diffstat (limited to 'notes.tex')
| -rw-r--r-- | notes.tex | 35 |
1 files changed, 21 insertions, 14 deletions
@@ -121,16 +121,16 @@ problem to get a reasonable solution: request. \end{enumerate} -Solutions \ref{over-serve}. and \ref{min-screen}. seem to lead to very complex -combinatorial problems (dynamic programming gives a running time of -$O(n2^{|T|})$). Solution \ref{fractional}. seem to be more realistic: what is -the point of having screens if you do not leverage their ability to change their -content frequently? +Solutions \ref{over-serve}. and \ref{min-screen}. seem to lead to very +complex combinatorial problems (dynamic programming gives a running +time of $O(n2^{|T|})$). Solution \ref{fractional}. seems to be more +realistic: what is the point of having screens if you do not leverage +their ability to change their content frequently? -Without taking the constraint of the advertisers into account (for each -advertiser, there is a subset of node where his ad can be displayed), the -optimization problem is simply choosing a subset of advertisers $A$ that -maximizes: +Without taking the constraint of the advertisers into account (for +each advertiser, there is a subset of node where his ad can be +displayed), the optimization problem is simply choosing a subset of +advertisers $A$ that maximizes: \begin{displaymath} \sum_{i\in A} b_i n_i \end{displaymath} @@ -138,15 +138,22 @@ subject to the constraint: \begin{displaymath} \sum_{i\in A} n_i \leq B \end{displaymath} -where $B$ is the number of views' capacity of the tree. This is nothing else -than a Knapsack Problem. In this case, the placement of ads has no importance: -the tree is just seen as a pool of available number of views that can be filled -continuously, and the position of ads has no importance. +where $B$ is the number of views' capacity of the tree. This is +nothing else than a Knapsack Problem. +\paragraph{Remarks} +\begin{itemize} +\item the placement of ads has no importance: the tree is simply seen + as a pool of available number of views that can be filled + continuously. +\item the topology of the graph has no impact on the problem, only the + number of nodes does. +\end{itemize} +Articles to read: \cite{Johnson:PCKP,DBLP:journals/telsys/ShawCC97} \bibliographystyle{plain} \bibliography{papers.bib} -\end{document}
\ No newline at end of file +\end{document} |