From a146d718108b39c2b5323245c399577f9cf1f14e Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Wed, 3 Jul 2013 10:17:46 -0700
Subject: paper

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

(limited to 'approximation.tex')

diff --git a/approximation.tex b/approximation.tex
index 670352b..7c3c47d 100644
--- a/approximation.tex
+++ b/approximation.tex
@@ -1,4 +1,4 @@
-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.
+Previous approaches towards designing truthful, budget feasible mechanisms for \textsc{Knapsack}~\cite{chen} and \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$. In the cases of \textsc{Knapsack} and~\textsc{Coverage}, as well as in the case of \EDP{},  monotonicity  prevents using traditional approximation algorithms.
 
 We address this issue by designing a convex relaxation of \EDP{}, and showing that it well approximates $OPT$. 
 
-- 
cgit v1.2.3-70-g09d2

