More space saving

1 files changed, 5 insertions, 7 deletions

diff --git a/related.tex b/related.tex
index 274f4fa..4c17d1f 100755
--- a/related.tex
+++ b/related.tex
@@ -3,11 +3,9 @@
 
 \junk{\subsection{Experimental Design} The classic experimental design problem, which we  review in Section~\ref{sec:edprelim}, deals with  which $k$ experiments to conduct among a set of $n$ possibilities. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature  \cite{pukelsheim2006optimal}; many involve a function of the covariance of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by its tractability and its relationship to the information gain.  %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem.
 }
-\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.}
-Budget feasible mechanism design was originally proposed by  \citeN{singer-mechanisms}, who considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model. %, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
-He shows that there exists a randomized, 112-approximation mechanism that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms.
-
-The above approximation guarantees hold for the expected value of the
+\noindent\emph{General Submodular Functions.}
+\citeN{singer-mechanisms} considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model. %, \emph{i.e.} assuming an  oracle providing the  value of the submodular objective on any given set. 
+He shows that there exists a randomized, 112-approximation mechanism that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen}  improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms. The above approximation guarantees hold for the expected value of the
 randomized mechanism: for a given
 instance, the approximation ratio provided by the mechanism may be
 unbounded. No deterministic, truthful, constant approximation mechanism that
@@ -15,7 +13,7 @@ runs in polynomial time is presently known for submodular maximization.
 Assuming access to an oracle providing the optimum in the
 full-information setup, Chen \emph{et al.}~propose a truthful, $8.34$-approximate mechanism; in cases for which the full-information problem is NP-hard, as \EDP, this mechanism is not poly-time, unless P=NP.  Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. 
 
-\noindent\emph{Budget Feasible Mechanism Design on Specific Problems.}
+\noindent\emph{Specific Problems.}
 Improved uper and lower bounds \emph{and} deterministic polynomial mechanisms are known for specific submodular objectives \cite{singer-mechanisms, chen, singer-influence}.
 \junk{For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer 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  deterministic mechanisms for \textsc{Knapsack} \cite{chen} and
@@ -40,7 +38,7 @@ Posted price, rather than direct revelation mechanisms, are also studied in \cit
 \noindent\emph{Monotone Approximations in Combinatorial Auctions.}
 Relaxations of combinatorial problems are prevalent
 in \emph{combinatorial auctions}, 
-in which an auctioneer aims at maximizing the social welfare. As noted by \citeN{archer-approximate},
+in which an auctioneer aims at maximizing social welfare. As noted by \citeN{archer-approximate},
 approximations to this maximization must preserve incentive compatibility. Most approximation
 algorithms do not preserve this property, hence specific relaxations, and corresponding roundings to an integral solution, must be
 constructed \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}. Because of the specificity of our relaxation, and because we seek a determinist mechanism and $\delta$-truthfulness, not truthfulness-in-expectation, none of the techniques present in these works apply to our setting.