From 6cd9d223c6beb635b9eec27bf666602551af879e Mon Sep 17 00:00:00 2001
From: Thibaut <thibaut.horel@gmail.com>
Date: Mon, 19 Dec 2011 19:37:13 -0800
Subject: Notes improvement

---
 notes.tex | 116 +++++++++++++++++++++++++++++++++++++-------------------------
 1 file changed, 70 insertions(+), 46 deletions(-)

(limited to 'notes.tex')

diff --git a/notes.tex b/notes.tex
index d24d77c..8e0ac80 100644
--- a/notes.tex
+++ b/notes.tex
@@ -4,7 +4,7 @@
 \begin{document}
 
 \section{Introduction}
-\paragraph{General problem} A user is evolving in an environment, understand how
+\paragraph{General problem} A user is moving in an environment, understand how
 to place ads in this environment.
 
 \paragraph{Model} The environment is a weighted directed graph, the vertices are
@@ -47,72 +47,87 @@ Two different types of problem:
   paper gives a 7-competitive algorithm against the optimal offline solution.
 \end{itemize}
 
-\paragraph{Restriction} The graph is a DAG: if the environment is well designed,
-the user shouldn't be passing through the same vertex twice.  Start first with a
-tree or even path and see if all the advertiser's requirements can be matched.
-
-Muthu's strategy: \emph{find the first non trivial problem and solve it}.
-
 \section{Static ads placement on a tree}
 
 \subsection{Notations}
 
-Let $T$ be a weighted tree: for each $u\in T$, $C(u)$ is the set of children of
-$u$. For all $v$ in $C(u)$, $p(v)$ will denote the probability of transition
-from vertex $u$ to vertex $v$. $T(u)$ is the tree rooted at $u$. $r$ is the root
-of the tree.
+Let $T$ be a weighted tree. For a node $u\in T$:
+\begin{itemize}
+\item $C(u)$ is the set of children of $u$
+\item $p(u,v)$ is the transition probability from $u$ to $v\in C(u)$
+\item $r$ is the root of the tree
+\end{itemize}
 
 For any function $f$ of the nodes, $f(T)$ will denote the expected return of a
-random walk on the tree starting at $r$, stopping when it reaches a leaf and
-where passing through vertex $v$ adds $f(u)$ to the return:
+random walk on the tree starting at $r$, stopping when it reaches a
+leaf and earning $f(u)$ for any visited node $u$:
 \begin{displaymath}
-  f(T)= f(r) + \sum_{v\in C(u)} p_v f(T(v))
+  f(T)= f(r) + \sum_{v\in C(r)} p(r,v) f\big(T(v)\big)
 \end{displaymath}
 
 Introducing the cumulative probabilities yields a simple expression for
 $f(T)$. Let $\lambda_u$ denote the probability of walking from the root of the
-tree to node $u$: $\lambda_u=\Pi_{i=1}^k p(u_k)$, with $u_1, \ldots, u_k$ the
+tree to node $u$: $\lambda_u=\Pi_{i=1}^{k-1} p(u_i,u_{i+1})$, with $u_1, \ldots, u_k$ the
 path from the root to $u$, then:
-
 \begin{displaymath}
   f(T)= \sum_{u\in T}\lambda_u f(u)
 \end{displaymath}
+note that the lambdas are decreasing along the branches of $T$. 
+
+For our purpose, $f$ will be the indicator function of a subset of
+nodes in $T$. For any $S\subset T$, $\mathbf{1}_S$ is defined by:
+\begin{displaymath}
+  \mathbf{1}_S(u) = \left\{
+    \begin{array}{ll}
+      1\quad \mathrm{if}\; u\in S\\
+      0\quad\mathrm{otherwise}
+    \end{array}
+  \right.
+\end{displaymath}
+$\mathbf{1}_S(T)=\sum_{u\in S}\lambda_u$ is simply the expected number
+of views of nodes in $S$ for a user walking in the tree. The lambdas
+can then be seen as capacities in terms of number of views. $B$ will
+denote the overall capacity of the tree: $\mathbf{1}_T(T)$.
 
 \subsection{Problem}
 
-There is a set of $n$ advertisers. $b_i$ is the per-impression value
-of advertiser $i$ and $n_i$ the expected number of times advertiser
-$i$ would like his ad to be seen.
+There is a set of $n$ advertisers. For advertiser $i$:
+\begin{itemize}
+\item $b_i$ is his per-impression value
+\item $n_i$ is his requested number of impressions  
+\end{itemize}
 
 An assignment is a subset $A$ of advertisers and a collection of subsets of $T$:
 $(A_i)_{i\in S}$. The elements of $A_i$ are the vertices of $T$ where the ad of
 advertiser $i$ will be displayed. The overall return of advertiser $i$ is simply
-$R_i = f_i(T)$ with $f_i:u\mapsto b_i\mathbf{1}_{A_i}(u)$.
+$R_i = \mathbf{1}_{A_i}(T)$.
 
 The goal is to find an assignment which maximizes the social welfare:
 \begin{equation}\label{eq:opt}
   W = \sum_{i\in A} R_i = \sum_{i\in A} b_i \mathbf{1}_{A_i}(T)
-\end{equation} with respect to the constraint:
-
+\end{equation} with respect to the constraints:
 \begin{equation}\label{eq:constraint} 
   \forall A_i,\; \mathbf{1}_{A_i}(T)\geq n_i
 \end{equation}
-
-If \eqref{eq:constraint} is the only constraint, then the optimization problem
-is trivial: select the advertiser whose $b_i n_i$ is the greatest and place his
-ad on all the nodes of the tree. However, by doing this $\mathbf{1}_{A_i}(T)$
-could be much greater than $n_i$. There are three ways of further refining the
-problem to get a reasonable solution:
+\begin{equation}
+  \sum_{i\in A} \mathbf{1}_{A_i}(T) \leq B
+\end{equation}
+without any other constraint, the optimization problem is trivial:
+select the advertiser whose $b_i n_i$ is the greatest and place his ad
+on all the nodes of the tree. However, by doing this
+$\mathbf{1}_{A_i}(T)$ could be much greater than $n_i$. There are
+three ways of further refining the problem to get a reasonable
+solution:
 \begin{enumerate}
-\item\label{over-serve} replacing $\mathbf{1}_{A_i}(T)$ by $n_i$ in
+\item\label{over-serve} \emph{Free disposal:} replacing $\mathbf{1}_{A_i}(T)$ by $n_i$ in
   \eqref{eq:opt}. In other words, even if the publisher over-serve an
   advertiser's request, he will not receive more than what the advertiser was
   initially willing to pay for.
-\item\label{min-screen} adding the constraint $\mathbf{1}_{A_i}(T)\leq n_i +
+\item\label{min-screen} \emph{One screen margin:} adding the constraint $\mathbf{1}_{A_i}(T)\leq n_i +
   \max_{x\in A_i} \lambda_x$: this simply expresses that removing any screen to
   the set of screens assigned to advertiser $i$ will lead to under-serving his
   request.
-\item\label{fractional} allow fractional occupation of a screen by an ad: in
+\item\label{fractional} \emph{Fractional allocation:} allow fractional occupation of a screen by an ad: in
   addition to choosing a set of screen for advertiser $i$, you can also choose
   for each screen a fraction of the time this ad will be displayed on the
   screen. This way, the screen can be share between several ads by doing a
@@ -121,16 +136,11 @@ 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}. 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:
+\subsection{Trivial Case}
+For now we will assume \emph{Fractional allocation}. In this case we
+can now serve each request exactly, \eqref{eq:constraint} is
+automatically true, and we only need to find a subset $A$ of
+advertisers that maximizes:
 \begin{displaymath}
   \sum_{i\in A} b_i n_i
 \end{displaymath}
@@ -138,19 +148,33 @@ 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.
+This is nothing else than a knapsack problem where $b_i n_i$ is the
+value of object $i$, $n_i$ is its weight and $B$ is the capacity of
+the knapsack.
 
 \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.
+  continuously in any order.
+\item the topology of the graph has no impact on the problem.
+\end{itemize}
+
+\subsection{Contiguous placement}
+
+To make the problem more interesting we add the following two
+constraints:
+\begin{itemize}
+\item if one ad appears on more than one screen in a branch of the
+  tree, the screens must be contiguous
+\item no ad must be seen on more than two screens
 \end{itemize}
 
+\subsubsection{Case of the path}
+
+
+
 Articles to read: \cite{Johnson:PCKP,DBLP:journals/telsys/ShawCC97}
 
 \bibliographystyle{plain}
-- 
cgit v1.2.3-70-g09d2

