From bc7134421f286f3ae497c202a45c83d19f585b46 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 30 Oct 2012 18:40:17 +0100
Subject: Some cleanup of the relaxation part

---
 main.tex | 37 ++++++++++++++++++++-----------------
 1 file changed, 20 insertions(+), 17 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 44be4e8..44851c1 100644
--- a/main.tex
+++ b/main.tex
@@ -241,22 +241,18 @@ gives the result of the theorem.
 
 \subsection{Relaxations of the value function}\label{sec:relaxation}
 
-To prove lemma~\ref{lemma:relaxation}, we use a general called pipage rounding
-introduced in \cite{pipage}.
-To prove lemma TODO, we will use a general method called pipage rounding,
-introduced in TODO. Two consecutive relaxations are used: the one that we are
-interested in, whose optimization can be computed efficiently, and the
-multilinear extension which presents a \emph{cross-convexity} like behavior
-which allows for rounding of fractional solution without decreasing the value
-of the objective function and thus ensures a constant approximation of the
-value function. The difficulty resides in showing that the ratio of the two
-relaxations is bounded.
-
-We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is a relaxation of the
-value function $V$ over $\mathcal{N}$ if it coincides with $V$ at binary
-points. Formally, for any $S\subseteq\mathcal{N}$, let $\mathbf{1}_S$ denote the
-indicator vector of $S$. $R_\mathcal{N}$ is a relaxation of $V$ over
-$\mathcal{N}$ iff:
+To prove lemma~\ref{lemma:relaxation}, we use a general method called pipage
+rounding introduced in \cite{pipage}. This method relies on \emph{piping} two
+relaxations of the value function, one being the \emph{multilinear extension}
+introduced below, the other one being the relaxation $L_\mathcal{N}$ already
+introduced in our mechanism. At each position of the pipe, we show that we keep
+a bounded approximation ratio to the original value function.
+
+We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is
+a relaxation of the value function $V$ over $\mathcal{N}$ if it coincides with
+$V$ at binary points. Formally, for any $S\subseteq\mathcal{N}$, let
+$\mathbf{1}_S$ denote the indicator vector of $S$. $R_\mathcal{N}$ is
+a relaxation of $V$ over $\mathcal{N}$ iff:
 \begin{displaymath}
     \forall S\subseteq\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
 \end{displaymath}
@@ -321,6 +317,13 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{multline*}
 \end{proof}
 
+It has been observed already that the multilinear extension presents the
+cross-convexity property: it is convex along any direction $e_i-e_j$ where $e_i$
+and $e_j$ are two elements of the canonical basis. This property allows to
+trade between two fractional components of a point without diminishing the
+value of the relaxation. The following lemma follows from the same idea but
+also ensures that the points remain feasible during the trade. 
+
 \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
@@ -519,7 +522,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \end{align*}
 \end{proof}
 
-We can now prove lemma TODO from previous section.
+We can now prove lemma~\ref{lemma:relaxation} from previous section.
 
 \begin{proof}
     Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*)
-- 
cgit v1.2.3-70-g09d2