From aff4f327939dd4ddeec81a4024b38e765abba99d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 8 Jul 2013 10:13:01 -0700
Subject: abstract typo

---
 abstract.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'abstract.tex')

diff --git a/abstract.tex b/abstract.tex
index bf078d0..54aebec 100644
--- a/abstract.tex
+++ b/abstract.tex
@@ -19,6 +19,6 @@ Each subject $i$ declares an associated cost $c_i >0$ to be part of the experime
 mechanism for \SEDP{} with suitable properties. 
 
 We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant factor  approximation to \EDP. 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}$.
-By applying previous work on budget feasible mechanisms with submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized  polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation.  We also show how to generalize our approach to a wide class of learning problems, beyond linear regression. 
+By applying previous work on budget feasible mechanisms with a submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized  polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation.  We also show how to generalize our approach to a wide class of learning problems, beyond linear regression. 
 
 
-- 
cgit v1.2.3-70-g09d2

