blob: 64ca77e6dc85077e719c2409363929af38033aeb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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}
|
