diff options
| author | Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local> | 2013-09-22 22:52:58 +0200 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local> | 2013-09-22 22:52:58 +0200 |
| commit | 6989616462eea7f534d17bb6aa7ebdf4e172db4d (patch) | |
| tree | 51ddc0d484c62cbd1edb44979070328274fc277c /approximation.tex | |
| parent | 0fb4e5a3e0beaf39e21273f4b0fdf7be92137f67 (diff) | |
| download | recommendation-6989616462eea7f534d17bb6aa7ebdf4e172db4d.tar.gz | |
small
Diffstat (limited to 'approximation.tex')
| -rwxr-xr-x | approximation.tex | 7 |
1 files changed, 3 insertions, 4 deletions
diff --git a/approximation.tex b/approximation.tex index 1b94615..546961f 100755 --- a/approximation.tex +++ b/approximation.tex @@ -123,13 +123,12 @@ Nevertheless, we prove that it is possible to use the barrier method to construc for all $i\in \mathcal{N},x\in\reals^n, \mu\geq\delta,$ %\end{equation} where $e_i$ is the $i$-th canonical basis vector of $\reals^n$. -In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$. In particular, the following proposition holds: +In other words, $f$ is $\delta$-decreasing if increasing any coordinate by $\delta$ or more at input $x$ ensures that the output will be at most $f(x)$. The following holds: \begin{proposition}\label{prop:monotonicity} For any $\delta\in(0,1]$ and any $\varepsilon\in(0,1]$, - Algorithm~\ref{alg:monotone} computes a $\delta$-decreasing, + there exists an algorithm 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{B}{b\varepsilon\delta})\big)$. \end{proposition} - -The description of Algorithm~\ref{alg:monotone} as well as the proof of the proposition can be found in Appendix~\ref{proofofproprelaxation}. +The proof and the algorithm (Algorithm~\ref{alg:monotone}) are in Appendix~\ref{proofofproprelaxation}. |
