From 20b0b3120e47d8afa3382fcaa643fd13560525fa Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 5 Nov 2012 07:12:01 -0800 Subject: muthu --- related.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'related.tex') diff --git a/related.tex b/related.tex index f61abc4..ec22041 100644 --- a/related.tex +++ b/related.tex @@ -1,5 +1,5 @@ \section{Related work} - +\label{sec:related} Budget feasible mechanism design was originally proposed by Singer \cite{singer-mechanisms}. Singer 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. Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). Chen \emph{et al.}~\cite{chen} improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful mechanisms for submodular maximization. -- cgit v1.2.3-70-g09d2