Add paper

1 files changed, 76 insertions, 0 deletions

diff --git a/paper/sections/appendix.tex b/paper/sections/appendix.tex
new file mode 100644
index 0000000..64ca77e
--- /dev/null
+++ b/paper/sections/appendix.tex
@@ -0,0 +1,76 @@
+
+\noindent \textbf{From expectation to high probability.}
+
+%\begin{lemma}\label{lemma:nd}
+%    Let $A\subseteq\mathcal{U}$ and $x=(v,c)\in\mathcal{U}\setminus A$, then
+%    the function $b\mapsto \mathcal{O}(A\cup\{x\},b)-\mathcal{O}(A,b)$ is
+%    non-decreasing over $\reals^+$.
+%\end{lemma}
+
+
+
+
+
+
+\begin{proof}[of Proposition~\ref{main_result}]
+    For each realization of the neighbors $R$, let us define by $X_R$ the
+    random set which includes each $u\in R$ with probability $q_u$ on the
+    second day and:
+    \begin{displaymath}
+        \tilde{X}_R=
+    \begin{cases}
+        X_R&\text{if } |X_R|\leq t\\
+        \emptyset&\text{otherwise}
+    \end{cases}
+    \end{displaymath}
+    where $t = k-|S|$. $\tilde{X}_R$ is a random variable over the feasible
+    solutions on the second day. As a consequence:
+    \begin{displaymath}
+        A(S) \geq \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big]
+    \end{displaymath}
+    Let us define by $Y$ the random set which includes each $u\in\neigh{X}$
+    with probability $p_uq_u$ and:
+    \begin{displaymath}
+        \tilde{Y}=
+        \begin{cases}
+            Y&\text{if } |Y|\leq t\\
+            \emptyset&\text{otherwise}
+        \end{cases}.
+    \end{displaymath}
+    It is easy to see that $\tilde{X}_R$ is the conditional expectation of
+    $\tilde{Y}$ given
+    $R$. Hence:
+    \begin{displaymath}
+        \sum_{R\subseteq\neigh{S}} p_R\mathbb{E}\big[f(\tilde{X}_R)\big]
+        = \mathbb{E}\big[f(\tilde{Y})\big]
+    \end{displaymath}
+    But:
+    \begin{align*}
+        \mathbb{E}\big[f(\tilde{Y})\big]
+        &=\sum_{T\subseteq\neigh{X}}\mathbb{P}\big[\tilde{Y}=T\big]f(T)
+    = \sum_{\substack{T\subseteq\neigh{X}\\|T|\leq
+    t}}\mathbb{P}\big[Y=T\big]f(T)\\
+    &= \mathbb{E}\big[f(Y)\big]-\sum_{\substack{T\subseteq\neigh{X}\\|T|>
+    t}}\mathbb{P}\big[Y=T\big]f(T)
+    \end{align*}
+    Roughly:
+    \begin{displaymath}
+        \sum_{\substack{T\subseteq\neigh{X}\\|T|>
+        t}}\mathbb{P}\big[Y=T\big]f(T)\leq
+        \frac{1}{2}\mathbb{E}\big[f(Y)\big]
+    \end{displaymath}
+    Combining the above inequalities we get:
+    \begin{displaymath}
+        A(S)\geq \frac{1}{2} \mathbb{E}\big[f(Y)\big]
+    \end{displaymath}
+    But $\mathbb{E}\big[f(Y)\big]$ is precisely the value of the non-adaptive
+    solution computed by Algorithm~\ref{alg:comb} which is
+    a $\left(1-\frac{1}{e}\right)$ approximation of the
+    optimal non adaptive solution. Hence:
+    \begin{displaymath}
+        A(S) \geq \frac{1}{2}\left(1-\frac{1}{e}\right) OPT_{NA}
+    \end{displaymath}
+    Finally, we conclude with Proposition~\ref{prop:gap}
+\end{proof}
+
+