diff options
| -rw-r--r-- | notes.tex | 35 | ||||
| -rw-r--r-- | papers.bib | 27 |
2 files changed, 48 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} @@ -51,3 +51,30 @@ bibsource = {DBLP, http://dblp.uni-trier.de} } +@article{Johnson:PCKP, + author = {Johnson, D. S. and Niemi, K. A.}, + interhash = {c23744607ef3ff3bf587030dda6cc6db}, + intrahash = {06a17ed7c91bf8af5444c70137ec774c}, + journal = {MATHEMATICS OF OPERATIONS RESEARCH}, + number = 1, + pages = {1-14}, + title = {On Knapsacks, Partitions, and a New Dynamic +Programming Technique for Trees}, + volume = 8, + year = 1983, +} + +@article{DBLP:journals/telsys/ShawCC97, + author = {Dong X. Shaw and + Geon Cho and + Hsuliang Chang}, + title = {A depth-first dynamic programming procedure for the extended + tree knapsack problem in local access network design}, + journal = {Telecommunication Systems}, + volume = {7}, + number = {1-3}, + year = {1997}, + pages = {29-43}, + ee = {http://dx.doi.org/10.1023/A:1019103824623}, + bibsource = {DBLP, http://dblp.uni-trier.de} +}
\ No newline at end of file |