From 24fdab84d29f2d2fb0bd78a4c7ad7131100afe94 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 16 Dec 2013 17:23:26 -0500 Subject: More space saving --- approximation.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'approximation.tex') 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}. -- cgit v1.2.3-70-g09d2