From d8618b13eacfb5578e023bd4070dabe958548f2b Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Thu, 4 Jul 2013 09:40:25 -0700
Subject: minor

---
 approximation.tex | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'approximation.tex')

diff --git a/approximation.tex b/approximation.tex
index 10cf171..cc861e8 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -50,9 +50,9 @@ expectation of $V$ under the  distribution $P_\mathcal{N}^\lambda$:
 \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}. 
-For $V$ the value function given by \eqref{modified} that we study here, the
-multi-linear extension \eqref{eq:multi-linear} cannot be computed---let alone maximized---in
-polynomial time. Hence, we introduce a new extension $L:[0,1]^n\to\reals$:
+Contrary to problems such as \textsc{Knapsack}, the
+multi-linear extension \eqref{eq:multi-linear} cannot be optimized in
+polynomial time for  the value function $V$  that we study here, given by \eqref{modified}. Hence, we introduce a new extension $L:[0,1]^n\to\reals$:
 \begin{equation}\label{eq:our-relaxation}
 \forall\,\lambda\in[0,1]^n,\quad L(\lambda) \defeq
 \log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right)=
@@ -194,7 +194,7 @@ Our construction of a $\delta$-decreasing, $\varepsilon$-accurate approximator o
     For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$,
     Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing,
     $\varepsilon$-accurate approximation of $L^*_c$. The running time of the
-    algorithm is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$. \note{THIBAUT, IS THERE A BUDGET $B$ IN THE DENOM OF THE LOGLOG TERM?}
+    algorithm is $O\big(poly(n, d, \log\log\frac{1}{b\varepsilon\delta})\big)$. \note{THIBAUT, IS THERE A BUDGET $B$ IN THE NUMERATOR OF THE LOGLOG TERM?}
 \end{proposition}
-We note that the the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because when the optimal $\lambda\in \dom_c$ lies at the boundary, certain costs can be saturated: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy.
+We note that the the execution of the barrier method on the restricted set $\dom_{c,\alpha}$ is necessary. The algorithm's output when executed over the entire domain may not necessarily be $\delta$-decreasing, even when the approximation accuracy is small. This is because costs become saturated when the optimal $\lambda\in \dom_c$ lies at the boundary: increasing them has no effect on the objective. Forcing the optimization to happen ``off'' the boundary ensures that this does not occur, while taking $\alpha$ to be small ensures that this perturbation does not cost much in terms of approximation accuracy.
 
-- 
cgit v1.2.3-70-g09d2

