From 91db9186fa25585c02a035e99386f73c75ad2601 Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sun, 10 Feb 2013 18:08:15 -0800
Subject: intro markets and typos

---
 related.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'related.tex')

diff --git a/related.tex b/related.tex
index cf27b32..a4956e9 100644
--- a/related.tex
+++ b/related.tex
@@ -9,7 +9,7 @@ In contrast to the above results, no deterministic, truthful, constant approxima
 
 
 \subsection{Budget Feasible Mechanism Design on Specific Problems}
-Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives under the query oracle. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also 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-mechanisms,singer-influence}. Our results therefore extend the set of problems for which a deterministic, polynomial mechanism is known to include \SEDP.
+Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives under the value query model. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also 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-mechanisms,singer-influence}. Our results therefore extend the set of problems for which a deterministic, polynomial mechanism is known to include \SEDP.
 
 \subsection{Beyond Submodular Objectives}
 Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing  fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists
-- 
cgit v1.2.3-70-g09d2

