approx

1 files changed, 4 insertions, 0 deletions

diff --git a/approximation.tex b/approximation.tex
index 23dc212..670352b 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -1,3 +1,7 @@
+Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and the \textsc{Coverage}~\cite{singer-influence} build upon polynomial-time algorithms that compute an approximation of $OPT$, the optimal value in the full information case. Crucially, to be used in designing a truthful mechanism, such algorithms need also to be \emph{monotone}, in the sense that decreasing any of the costs $c_i$ leads to an increase of the estimate of $OPT$. Both in the cases of \textsc{Knapsack}~\cite{chen} and~\textsc{Coverage}, as well as in the case of \EDP{}, the monotonicity requirement prevents using traditional approximation algorithms for approximating any of the above problems.
+
+We address this issue by designing a convex relaxation of \EDP{}, and showing that it well approximates $OPT$. 
+
 As noted above, \EDP{} is NP-hard. Designing a mechanism for this problem, as
 we will see in Section~\ref{sec:mechanism}, will involve being able to find an approximation of its optimal value
 $OPT$ defined in \eqref{eq:non-strategic}. In addition to being computable in