summaryrefslogtreecommitdiffstats
path: root/general.tex
diff options
context:
space:
mode:
authorStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-05 00:49:55 -0800
committerStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2012-11-05 00:49:55 -0800
commite2395812a045d1319643a658bda8565e77e74dc9 (patch)
tree9e3a9b88611aea776bee6294f52d12e1aadef449 /general.tex
parent64b5cb571172477e68c8a16862a29ec617292677 (diff)
downloadrecommendation-e2395812a045d1319643a658bda8565e77e74dc9.tar.gz
gen
Diffstat (limited to 'general.tex')
-rw-r--r--general.tex8
1 files changed, 4 insertions, 4 deletions
diff --git a/general.tex b/general.tex
index 6e56577..75b87ad 100644
--- a/general.tex
+++ b/general.tex
@@ -32,8 +32,8 @@ a covariance $\sigma^2 I_d$, and the experimenter is solving a ridge regression
problem with penalty term $\norm{x}_2^2$.
Moreover, our results can be extended to the general Bayesian case, by
-replacing $I_d$ with the positive semidefinite matrix $R$. First, we set the
-origin of the value function so that $V(\emptyset) = 0$; we define:
+replacing $I_d$ with the positive semidefinite matrix $R$. First, we re-set the
+origin of the value function so that $V(\emptyset) = 0$:
\begin{align}\label{eq:normalized}
\tilde{V}(S)
& = \frac{1}{2}\log\det(R + \T{X_S}X_S) - \frac{1}{2}\log\det R\\
@@ -42,11 +42,11 @@ origin of the value function so that $V(\emptyset) = 0$; we define:
Applying the mechanism described in algorithm~\ref{mechanism} and adapting the
analysis of the approximation ratio, we get the following result which extends
-theorem~\ref{thm:main}:
+Theorem~\ref{thm:main}:
\begin{theorem}
There exists a truthful and budget feasible mechanism for the objective
- function $\tilde{V}$ \eqref{eq:normalized}. Furthermore, for any $\varepsilon
+ function $\tilde{V}$ given by \eqref{eq:normalized}. Furthermore, for any $\varepsilon
> 0$, in time $O(\text{poly}(|\mathcal{N}|, d, \log\log \varepsilon^{-1}))$,
the algorithm computes a set $S^*$ such that:
\begin{displaymath}