summaryrefslogtreecommitdiffstats
path: root/approximation.tex
diff options
context:
space:
mode:
authorThibaut Horel <thibaut.horel@gmail.com>2013-12-16 17:23:26 -0500
committerThibaut Horel <thibaut.horel@gmail.com>2013-12-16 17:23:26 -0500
commit24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 (patch)
treec39c845a77150d002aaa1e212725f9e260c152a1 /approximation.tex
parent9c7c18014f41ad1cd52404b69109d83dd6f6acc9 (diff)
downloadrecommendation-24fdab84d29f2d2fb0bd78a4c7ad7131100afe94.tar.gz
More space saving
Diffstat (limited to 'approximation.tex')
-rwxr-xr-xapproximation.tex4
1 files changed, 2 insertions, 2 deletions
diff --git a/approximation.tex b/approximation.tex
index 2747d5a..bab2c93 100755
--- a/approximation.tex
+++ b/approximation.tex
@@ -129,7 +129,7 @@ In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\del
We achieve this by restricting the optimization over a subset of $\dom_c$ at which the concave relaxation $L$ is ``sufficiently'' concave. Formally, for $\alpha\geq 0$ let
$$\textstyle\dom_{c,\alpha} \defeq \{\lambda \in [\alpha,1]^n: \sum_{i\in \mathcal{N}}c_i\lambda_i \leq B\}\subseteq \dom_c . $$
-Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concave relaxation \eqref{eq:primal}:
+Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbed problem:
\begin{align}\tag{$P_{c,\alpha}$}\label{eq:perturbed-primal}
\begin{split} \text{Maximize:} &\qquad L(\lambda)\\
\text{subject to:} & \qquad\lambda \in \dom_{c,\alpha}
@@ -144,4 +144,4 @@ Note that $\dom_c=\dom_{c,0}.$ Consider the following perturbation of the concav
$L^*_c$. The running time of the algorithm is $O\big(poly(n, d,
\log\log\frac{B}{b\varepsilon\delta})\big)$.
\end{proposition}
-The proof and the formal description of the algorithm are in \cite{arxiv}.
+The proof can be found in \cite{arxiv}.