From ff48f359b3b0bd0bd1b7252457bfd9fce71ed545 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Mon, 5 Nov 2012 10:25:58 -0800
Subject: removed erroneous statement

---
 problem.tex | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index 527c34a..f313be0 100644
--- a/problem.tex
+++ b/problem.tex
@@ -146,7 +146,8 @@ Ideally, motivated by the $D$-optimality criterion, we would like to design a me
 We present our results with this version of the objective function because it is simple and captures the versions
 we will need later (including  an arbitrary matrix in place of $I_d$ or a zero matrix which will correspond to ~\eqref{dcrit} ).
 
-Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition, \eqref{edp}---and the equivalent problem with objective \eqref{dcrit}---are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Nevertheless, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$.
+%Note that maximizing \eqref{modified} is equivalent to maximizing \eqref{dcrit} in the full-information case. In particular, $\det(\T{X_S}X_S)> \det(\T{X_{S'}}X_{S'})$ iff $\det(I_d+\T{X_S}X_S)>\det(I_d+\T{X_{S'}}X_{S'})$. In addition,
+\EDP{} \emph{and} the corresponding problem with objective \eqref{dcrit} are NP-hard; to see this, note that \textsc{Knapsack} reduces to EDP with dimension $d=1$ by mapping the weight of each item $w_i$ to an experiment with $x_i=w_i$. Moreover, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$.
 %, allowing us to use the extensive machinery for the optimization of submodular functions, as well as recent results in the 
 % context of budget feasible auctions \cite{chen,singer-mechanisms}. 
 
@@ -162,7 +163,8 @@ For any $M>1$, there is no $M$-approximate, truthful, budget feasible, individua
 \begin{proof}
 \input{proof_of_lower_bound1}
 \end{proof}
-This negative result motivates us to study a problem with a modified objective:}\end{comment}
+This negative result motivates us to study a problem with a modified objective:}
+\end{comment}
 
 
 \begin{comment}
-- 
cgit v1.2.3-70-g09d2

