diff options
| -rw-r--r-- | main.tex | 47 |
1 files changed, 27 insertions, 20 deletions
@@ -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: |