diff options
| -rw-r--r-- | main.tex | 35 |
1 files changed, 19 insertions, 16 deletions
@@ -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. +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: +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^*) |