From 20b0b3120e47d8afa3382fcaa643fd13560525fa Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
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

