From 0be4d712f0f3757e22763a88b5a7e3459925394a Mon Sep 17 00:00:00 2001
From: Thibaut <thibaut.horel@gmail.com>
Date: Thu, 15 Dec 2011 18:24:17 -0800
Subject: Found two new articles to read.

---
 notes.tex  | 37 ++++++++++++++++++++++---------------
 papers.bib | 27 +++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 15 deletions(-)

diff --git a/notes.tex b/notes.tex
index 615f71b..d24d77c 100644
--- a/notes.tex
+++ b/notes.tex
@@ -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?
-
-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:
+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:
 \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}
diff --git a/papers.bib b/papers.bib
index e0793f2..d6cbbc9 100644
--- a/papers.bib
+++ b/papers.bib
@@ -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
-- 
cgit v1.2.3-70-g09d2