diff options
Diffstat (limited to 'approximation.tex')
| -rwxr-xr-x | approximation.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/approximation.tex b/approximation.tex index cc278e1..1b94615 100755 --- a/approximation.tex +++ b/approximation.tex @@ -47,7 +47,7 @@ expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) -= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\quad \lambda\in[0,1]^n. += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[ \log\det\big( I_d + \textstyle\sum_{i\in S} x_i\T{x_i}\big) \big],\quad \lambda\in[0,1]^n. \end{equation} Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. @@ -56,7 +56,7 @@ multi-linear extension \eqref{eq:multi-linear} cannot be optimized in polynomial time for the value function $V$ we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~ \begin{equation}\label{eq:our-relaxation} L(\lambda) \defeq -\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right), +\log\det\big(I_d + \textstyle\sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\big), %= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right), \quad \lambda\in[0,1]^n. \end{equation} |