Even more fixes in section 3

1 files changed, 27 insertions, 20 deletions

diff --git a/main.tex b/main.tex
index 56fba56..22754aa 100644
--- a/main.tex
+++ b/main.tex
@@ -322,10 +322,10 @@ However, for the purpose of proving theorem~\ref{thm:main}, we need to bound
 $L_\mathcal{N}$ from above (up to a multiplicative factor) by $V$. We use the
 \emph{pipage rounding} method from Ageev and Sviridenko \cite{pipage}, where
 $L_\mathcal{N}$ is first bounded from above by $F_\mathcal{N}$, which is itself
-subsequently bounded by $V$. While the latter part is general an can be apply
+subsequently bounded by $V$. While the latter part is general and can be apply
 to the multi-linear extension of any submodular function, the former part is
 specific to our choice for the function $L_\mathcal{N}$ and is our main
-technical contribution.
+technical contribution (lemma~\ref{lemma:relaxation-ratio}).
 
 First we prove a variant of the $\varepsilon$-convexity of the multi-linear
 extension \eqref{eq:multilinear} introduced by Ageev and Sviridenko
@@ -345,6 +345,12 @@ $\reals^{|\mathcal{N}|}$, then $\tilde{F}$ is convex. Hence its maximum over the
 is attained at one of the boundaries of $I_\lambda$ for which one of the $i$-th
 or the $j$-th component of $\lambda$ becomes integral.
 
+The lemma below proves that we can similarly trade one fractional component for
+an other until one of them becomes integral \emph{while maintaining the
+feasibility of the point at which $F_\mathcal{N}$ is evaluated}. Here, by feasibility of
+a point $\lambda$, we mean that it satisfies the budget constraint $\sum_{1\leq
+i\leq |\mathcal{N}|} \lambda_i c_i \leq B$.
+
 \begin{lemma}[Rounding]\label{lemma:rounding}
     For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible
     $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is
@@ -357,7 +363,7 @@ or the $j$-th component of $\lambda$ becomes integral.
 \begin{proof}
     We give a rounding procedure which given a feasible $\lambda$ with at least
     two fractional components, returns some $\lambda'$ with one less fractional
-    component, feasible such that:
+    component, feasible, and such that:
     \begin{displaymath}
         F_\mathcal{N}(\lambda) \leq F_\mathcal{N}(\lambda')
     \end{displaymath}
@@ -412,32 +418,33 @@ or the $j$-th component of $\lambda$ becomes integral.
 \end{lemma}
 
 \begin{proof}
-
     We will prove that $\frac{1}{2}$ is a lower bound of the ratio $\partial_i
-    F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$.
-
-    \stratis{what is $\partial_i?$}. 
-
-    This will be enough to conclude, by observing that:
+    F_\mathcal{N}(\lambda)/\partial_i L_\mathcal{N}(\lambda)$. Where
+    $\partial_i\, \cdot$ denotes the derivative of a function with respect to the
+    $i$-th variable. This will be enough to conclude, by observing that at
+    $\lambda = 0$, one can write:
     \begin{displaymath}
         \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
         \sim_{\lambda\rightarrow 0}
         \frac{\sum_{i\in \mathcal{N}}\lambda_i\partial_i F_\mathcal{N}(0)}
         {\sum_{i\in\mathcal{N}}\lambda_i\partial_i L_\mathcal{N}(0)}
+        \geq \frac{1}{2}
     \end{displaymath}
-    \stratis{what about other boundaries?}
-   and that an interior critical point of the ratio
-    $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$ is characterized by:
+    If the minimum is attained at a point interior to the hypercube, then it is
+    a critical point of the ratio
+    $F_\mathcal{N}(\lambda)/L_\mathcal{N}(\lambda)$. Such a critical point is
+    characterized by:
     \begin{displaymath}
         \frac{F_\mathcal{N}(\lambda)}{L_\mathcal{N}(\lambda)}
         = \frac{\partial_i F_\mathcal{N}(\lambda)}{\partial_i
-        L_\mathcal{N}(\lambda)}
+        L_\mathcal{N}(\lambda)} \geq \frac{1}{2}
     \end{displaymath}
-
+    
+    The case of the faces of the hypercube can be dealt with by induction
+    (TODO).
 
     Let us start by computing the derivatives of $F_\mathcal{N}$ and
-    $L_\mathcal{N}$ with respect to
-    the $i$-th component.
+    $L_\mathcal{N}$ with respect to the $i$-th component.
 
     For $F$, it suffices to look at the derivative of
     $P_\mathcal{N}^\lambda(S)$:
@@ -497,16 +504,16 @@ or the $j$-th component of $\lambda$ becomes integral.
     we get:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) 
-        & \geq \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        & = \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
         & \geq \frac{1}{2}
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_\mathcal{N}^\lambda(S)
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
         \log\Big(1 + \T{x_i}A(S)^{-1}x_i\Big)\\
         &\hspace{-3.5em}+\frac{1}{2}
         \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
-        P_\mathcal{N}^\lambda(S\cup\{i\})
+        P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})
         \log\Big(1 + \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
         &\geq \frac{1}{2}
         \sum_{S\subseteq\mathcal{N}}
@@ -516,7 +523,7 @@ or the $j$-th component of $\lambda$ becomes integral.
 
     Using that $A(S)\geq I_d$ we get that:
     \begin{displaymath}
-        \T{x_i}A(S)^{-1}x_i \leq 1 
+        \T{x_i}A(S)^{-1}x_i \leq \norm{x_i}_2^2 = 1 
     \end{displaymath}
     
     Moreover: