From c60b7918b8a69ea362da3a58e239ef089e7e358a Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 8 Jul 2013 14:02:27 -0700
Subject: eps

---
 intro.tex | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index e5ca357..1d07f48 100644
--- a/intro.tex
+++ b/intro.tex
@@ -38,7 +38,8 @@ subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budge
 \smallskip
 The objective function, which is the key, is formally obtained by optimizing  the information gain in  $\beta$ when the latter is learned  through ridge regression, and is related to  the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. 
 \item
-We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor  approximation to the optimal value of \eqref{obj}. In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and  $\log\log\frac{B}{\epsilon\delta}$. In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{}  within a factor 2 approximation. 
+We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and  $\log\log\frac{B}{\epsilon\delta}$. 
+In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{}  within a factor 2 approximation. 
 
 \smallskip
 We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time,  or a non-deterministic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded).
-- 
cgit v1.2.3-70-g09d2

