diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2016-02-29 19:39:56 -0500 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2016-02-29 19:39:56 -0500 |
| commit | 310718cb00370138b8d6f0e8a8222e5ecdda843c (patch) | |
| tree | 113938bc18de495bc555e146c5ab098a82d5095e /related.tex | |
| parent | 49880b3de9e4a4a190e26d03dbe093e3534823de (diff) | |
| download | recommendation-master.tar.gz | |
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, |