Notes: case of the pathHEADmaster

1 files changed, 42 insertions, 8 deletions

diff --git a/notes.tex b/notes.tex
index 8e0ac80..b8a77d1 100644
--- a/notes.tex
+++ b/notes.tex
@@ -1,6 +1,7 @@
 \documentclass{article}
 \usepackage[utf8]{inputenc}
-\usepackage{amsmath}
+\usepackage{amsmath,amsthm}
+\newtheorem{lemma}{Lemma}
 \begin{document}
 
 \section{Introduction}
@@ -137,7 +138,7 @@ solution:
 \end{enumerate}
 
 \subsection{Trivial Case}
-For now we will assume \emph{Fractional allocation}. In this case we
+From now on 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:
@@ -165,17 +166,50 @@ the knapsack.
 
 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}
+\begin{enumerate}
+\item\label{con:cont} if one ad appears on more than one screen in a branch, the screens must be contiguous
+\item\label{con:limit} no ad must be seen on more than two screens
+\end{enumerate}
 
 \subsubsection{Case of the path}
 
+An allocation will be called \emph{feasible} if it satisfies the two
+afore-mentioned constraints.
+
+\begin{lemma}
+  Reordering the ads by decreasing order of $n_i$ in a feasible
+  allocation only breaks the constraint \ref{con:limit}. by one screen:
+  no ad is seen on more than three contiguous screens.
+\end{lemma}
+
+\begin{proof}
+  Case disjunction and lots of trivial inequalities but it works. The
+  fact that the capacities of the nodes are decreasing along a branch is
+  important (this is the first time the topology of the graph is used).
+\end{proof}
+
+This lemma gives a way to find an approximation of the optimal
+solution using dynamic programming: consider the ads by increasing
+order of $n_i$ and start packing them from the bottom.
+
+\paragraph{Question:} the $n_i$ are not necessarily integers, we can
+do rounding. What is the typical precision needed?
+
+\paragraph{Price of anarchy:} The greedy dynamic programming algorithm
+will have a global welfare greater than the optimal feasible
+allocation. Looking at how the algorithm proceeds, for each
+advertiser, we exceed the optimal solution by at most the capacity of
+the node we are currently filling. Does this show that the price of
+anarchy is bounded by 2? It seems that this gives a bound on the Price
+of Stability. This bound could potentially be proven tight by a simple
+example.
+
+\subsubsection{Case of the tree}
+
+Try to find a swapping argument similar to the one used for the path.
 
 
-Articles to read: \cite{Johnson:PCKP,DBLP:journals/telsys/ShawCC97}
+\nocite{Johnson:PCKP,DBLP:journals/telsys/ShawCC97}
 
 \bibliographystyle{plain}
 \bibliography{papers.bib}