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 ++++++++++++++++++++++---------------
 1 file changed, 22 insertions(+), 15 deletions(-)

(limited to 'notes.tex')

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}
-- 
cgit v1.2.3-70-g09d2