From de9f4d9820ce6a879bcc82f25334510e013f052d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 7 Jul 2013 11:25:03 -0700
Subject: related

---
 related.tex | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index 88a0171..f929c75 100644
--- a/related.tex
+++ b/related.tex
@@ -42,8 +42,9 @@ a truthful, $O(\log^3 n)$-approximate mechanism
 Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}.
 
 \paragraph{Relaxations in Mechanism Design}
-Beyond budget feasible mechanisms, relaxations of combinatorial problems are prevalent
-in \emph{combinatorial auctions} \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. In such auctions, 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},
+Relaxations of combinatorial problems are prevalent
+in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}, 
+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
@@ -56,12 +57,10 @@ ratio in \cite{archer-approximate}, by treating the fractional solution of a lin
 Beyond LP relaxations, 
 \citeN{dughmi2011convex} propose
 truthful-in-expectation mechanisms for combinatorial auctions in which
-the bidders' utilities are matroid rank sum functions (applied earlier to the combinatorial public procjects problem \cite{dughmi-truthful}). As in our case, their framework relies
+the bidders' utilities are matroid rank sum functions (applied earlier to the \textsc{CombinatorialPublicProjects} problem \cite{dughmi-truthful}). As in our case, their framework relies
 on solving a convex optimization problem and ensuring that it is
 ``well-conditioned'', resembling the technical challenge we face in
-Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation; in addition, our objective is not a matroid rank sum function, so the convex relaxation applied in \cite{dughmi2011convex} does not readily extend to \EDP.
-
-
+Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation; in addition, our objective is not a matroid rank sum function, so the approximation guarantees of convex relaxation  in \cite{dughmi2011convex} do not readily extend to \EDP.
 Closer to us, \citeN{briest-approximation} \ldots. However, we \ldots \note{NEEDS TO BE FIXED!}
 
 \begin{comment}
-- 
cgit v1.2.3-70-g09d2

