diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-05 00:49:55 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2012-11-05 00:49:55 -0800 |
| commit | e2395812a045d1319643a658bda8565e77e74dc9 (patch) | |
| tree | 9e3a9b88611aea776bee6294f52d12e1aadef449 /general.tex | |
| parent | 64b5cb571172477e68c8a16862a29ec617292677 (diff) | |
| download | recommendation-e2395812a045d1319643a658bda8565e77e74dc9.tar.gz | |
gen
Diffstat (limited to 'general.tex')
| -rw-r--r-- | general.tex | 8 |
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} |
