From 310718cb00370138b8d6f0e8a8222e5ecdda843c Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Mon, 29 Feb 2016 19:39:56 -0500 Subject: Change to ACM style and inlining of the proofs --- related.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'related.tex') diff --git a/related.tex b/related.tex index 60bc295..e160de6 100644 --- a/related.tex +++ b/related.tex @@ -16,7 +16,7 @@ full-information setup, Chen \emph{et al.}~propose a truthful, $8.34$-approximat \vspace{0.5\baselineskip} \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}. +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 \textsc{Coverage} \cite{singer-influence} follow the same general framework, -- cgit v1.2.3-70-g09d2