Fist reduction of the main part

1 files changed, 3 insertions, 3 deletions

diff --git a/abstract.tex b/abstract.tex
index 9e99fcd..4cff1cd 100644
--- a/abstract.tex
+++ b/abstract.tex
@@ -1,5 +1,5 @@
 %We initiate the study of mechanisms for \emph{experimental design}. 
-
+\begin{comment}
 In the classical {\em experimental design} setting,
 an  experimenter  \E\ 
 %with  a budget $B$ 
@@ -17,8 +17,8 @@ As a proxy for various practical constraints, \E{} may select only a subset of s
 We initiate the study of budgeted mechanisms for experimental design. In this setting,  \E{} has a budget $B$.  
 Each subject $i$ declares an associated cost $c_i >0$ to be part of the experiment, and must be paid at least her cost.  In particular,  the {\em  Experimental Design Problem} (\SEDP) is to find a set $S$ of subjects for the experiment that maximizes $V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in S}c_i\leq B$; our objective function corresponds to  the information gain in  parameter  $\beta$ that is learned through linear regression methods, and is related to the so-called $D$-optimality criterion.  Further,  the subjects  are \emph{strategic} and may lie about their costs. Thus, we need to design a 
 mechanism for \SEDP{} with suitable properties. 
-
-We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant ($\approx 12.98$) 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}$.
+\end{comment}
+We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant ($\approx 12.98$) factor  approximation for the \emph{Experimental Design Problem} (\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 a submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized  polynomial time mechanism. We also establish that no truthful, budget-feasible mechanism is possible within a factor $2$ approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.