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 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}. |