diff options
Diffstat (limited to 'related.tex')
| -rw-r--r-- | related.tex | 2 |
1 files changed, 1 insertions, 1 deletions
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, |