From 1b985ce54bd720561b88d756b28a3957fc9a3c6d Mon Sep 17 00:00:00 2001
From: Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>
Date: Sat, 3 Nov 2012 10:17:01 -0700
Subject: related

---
 intro.tex | 53 +----------------------------------------------------
 1 file changed, 1 insertion(+), 52 deletions(-)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index 0b5b70f..72cdd96 100644
--- a/intro.tex
+++ b/intro.tex
@@ -14,55 +14,4 @@
     machine learning problems
 \end{itemize}
 
-\subsection{Related work}
-
-Two types of mechanisms: \emph{deterministic} and \emph{randomized}. For
-randomized mechanisms, people seek \emph{universally truthful} mechanisms:
-mechanisms which are a randomization of truthful mechanisms.
-
-\paragraph{Symmetric submodular functions} $V(S) = g(|S|)$ where $g$ is
-a concave function. Truthful deterministic mechanism with approximation ratio
-of 2. This is optimal \cite{singer-mechanisms}.
-
-\paragraph{Knapsack} deterministic: $1+\sqrt{2}\leq \alpha \leq 2 + \sqrt{2}$,
-randomized: $2\leq \alpha\leq 3$ \cite{chen}
-
-\paragraph{Matching} deterministic: $2 \leq \alpha\leq 7.32$ \cite{singer-mechanisms}
-
-\paragraph{Coverage} deterministic: $ ?\leq\alpha\leq 31$ \cite{singer-influence}
-
-\paragraph{Submodular function} deterministic: $1+\sqrt{2}\leq\alpha\leq ?$,
-randomized: $2\leq\alpha\leq 7.91$ \cite{chen}
-
-For wider class of functions, \cite{singer-mechanisms} proves that even for XOS
-functions, the lower bound is $\sqrt{n}$ (no constant approximation) even in the
-non-strategic case). To be able to say something interesting, people extend the
-computational model to the \emph{demand} query model: you have access to an
-oracle which given a vector of price $[p_i]_{i\in\mathcal{N}}$ returns
-$S\in\argmax_{S\subseteq\mathcal{N}} V(S) - \sum_{i\in S} p_i$
-
-\paragraph{XOS functions} fractionally additive functions: functions which can
-be written as the max of a finite set of additive functions. deterministic: 768
-
-\paragraph{Complement-free (sub-additive) objective} derministic: $O(\log^3 n)$
-\cite{dobz2011-mechanisms}. randomized: $O(\frac{\log n}{\log \log n})$
-\cite{bei2012budget}. More generally \cite{bei2012budget} gives a randomized
-mechanism which is $O(\mathcal{I})$ where $\mathcal{I}$ is the integrality gap
-of a set cover like problem which is defined from the value function. In
-particular, for XOS function, this integrality gap is $O(1)$.
-
-\paragraph{Bayesian mechanism design} when we have a distribution over the
-costs of the agents. In this case the approximation guarantee is defined in
-expectations. \cite{bei2012budget} $768/512$ approximation ratio for any
-subadditive function.
-
-\paragraph{Online mechanisms} \cite{learning} in the i.i.d posted price model
-for symmetric submodular functions randomized $O(1)$-competitive algorithm. For
-general submodular function in the secretary posted price model randomized
-$O(\log n)$-competitive algorithm. In the bidding model $O(1)$-competitive
-algorithm.
-
-\stratis{What is known about the maximization of logdet in the non-strategic case? Is it NP hard? Approximation ratios?}
-\thibaut{Knapsack reduces to our problem in dimension 1, hence maximizing log
-det is NP-hard. The approximation ratio is at least (1-1/e) by applying the
-general approximation algorithm from Sviridenko \cite{sviridenko-submodular}.}
+\input{related}
-- 
cgit v1.2.3-70-g09d2

