From 8562564268f83ca4ea0a4d6cd316a61f8b66f6b2 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 21:21:23 -0700
Subject: minor

---
 related.tex | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index 6cf059f..b25b91b 100644
--- a/related.tex
+++ b/related.tex
@@ -19,12 +19,11 @@ full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approxima
 \paragraph{Budget Feasible Mechanism Design on Specific Problems}
 Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate  mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. 
 
-The above deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
+The  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
 \textsc{Coverage} \cite{singer-influence} follow the same general framework,
-which we also employ. We describe this framework in detail in
+which we also employ in our mechanism for \EDP. We describe this framework in detail in
 Section~\ref{sec:main}. Both of these mechanisms rely on approximating the
-optimal solution to the underlying combinatorial problem by a well-known LP
-relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No
+optimal solution to the underlying combinatorial problem by a well-known linear program (LP) relaxation~\cite{pipage}, which can be solved exactly in polynomial time. No
 such  relaxation exists for \EDP, whose logarithmic objective is unlikely to be
 approximable through an LP. We develop instead a convex relaxation to \EDP;
 though, contrary to the above LP relaxations, this cannot be solved exactly, we
@@ -47,12 +46,11 @@ in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughm
 in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate},
 approximations to this maximization must preserve incentive compatibility and truthfulness. Most approximation
 algorithms do not preserve these properties, hence specific relaxations, and corresponding roundings to an integral solution, must be
-constructed. \citeN{archer-approximate} propose a randomized rounding of the linear
-programming relaxation of the \textsc{SetPacking} problem, yielding a mechanism
+constructed. \citeN{archer-approximate} propose a randomized rounding of the LP relaxation of the \textsc{SetPacking} problem, yielding a mechanism
 which is \emph{truthful-in-expectation}. %and in high probability. 
 \citeN{lavi-truthful} construct randomized
 truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation
-ratio in \cite{archer-approximate}, by treating the fractional solution of a linear program as a probability distribution over integral solutions. 
+ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution over integral solutions. 
 
 Beyond LP relaxations, 
 \citeN{dughmi2011convex} propose
-- 
cgit v1.2.3-70-g09d2

