From cbb16c62f10115a0927848ab0ad5aa43a47ab2c7 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 3 Nov 2012 18:33:39 -0700
Subject: edp2

---
 problem.tex | 1 +
 1 file changed, 1 insertion(+)

(limited to 'problem.tex')

diff --git a/problem.tex b/problem.tex
index b8e6af8..5631f7a 100644
--- a/problem.tex
+++ b/problem.tex
@@ -153,6 +153,7 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t
 
 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 satifies $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}. 
 
+\stratis{A potential problem is that all of the above properties hold also for, \emph{e.g.}, $V(S)=\log(1+\det(\T{X_S}X_S))$\ldots}
 
 
 \begin{comment}
-- 
cgit v1.2.3-70-g09d2

