diff options
| -rw-r--r-- | final/main.tex | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/final/main.tex b/final/main.tex index 6f751df..0258e07 100644 --- a/final/main.tex +++ b/final/main.tex @@ -523,10 +523,32 @@ extended, having made the appropriate changes, to the constrained case) as in th Lemma~6 from \cite{babaioff} yields the following version of the core decomposition lemma: -\begin{conjecture} +\begin{lemma} $\Rev(\hat{x}, D)\leq \Val(D^C_\emptyset) + \sum_A p_A\Rev(\hat{x}_A, D^T_A)$. -\end{conjecture} +\end{lemma} + +\begin{proof} + Similarly to the proof of Lemma 6 in \cite{babaioff}, we get: + \begin{displaymath} + \Rev(\hat{x}, D) \leq \sum_A p_A \Rev(\hat{x}_A, D_A) + \end{displaymath} + Using Corollary~\ref{cor}, we get that $\Rev(\hat{x}_A, D_A) + \leq \Val(D_A^C) + \Rev(\hat{x}_A, D_A^T)$. Hence: + \begin{align*} + \Rev(\hat{x}, D) &\leq \sum_A p_A\big(\Val(D_A^C) + \Rev(\hat{x}_A, + D_A^T) \big)\\ + &= \sum_A p_A\Val(D_A^C) + \sum_A p_A \Rev(\hat{x}_A, + D_A)\\ + &\leq \sum_A p_A\Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A, + D_A)\\ + &= \Val(D_{\emptyset}^C) + \sum_A p_A \Rev(\hat{x}_A, + D_A) + \end{align*} + Where the second inequality used that $\Val(D_A^C)\leq + \Val(D_{\emptyset}^C)$ and where the last equality used $\sum_A p_A = 1$. +\end{proof} + However, if we keep pushing in this direction, it seems that the approach fails when trying to obtain the following: |