diff options
| author | Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local> | 2013-09-22 07:55:14 +0200 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@Stratiss-MacBook-Air.local> | 2013-09-22 07:55:14 +0200 |
| commit | cc1eea524d8fd1314d85fe7b56cddd95fd75302d (patch) | |
| tree | 8d028b58c801d7263e2457e5cf9934e279b51e70 /related.tex | |
| parent | 1cb6e4b28e77b8c1a87e54bbd7097d7f8af0e371 (diff) | |
| parent | 50900bfc44961b87379cd2d3464b677d9f5be1ac (diff) | |
| download | recommendation-cc1eea524d8fd1314d85fe7b56cddd95fd75302d.tar.gz | |
Merge branch 'master' of ssh://74.95.195.229:1444/git/data_value
Diffstat (limited to 'related.tex')
| -rwxr-xr-x | related.tex | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/related.tex b/related.tex index 4b7e740..8cca712 100755 --- a/related.tex +++ b/related.tex @@ -36,7 +36,7 @@ establish that it can be incorporated in the framework of \paragraph{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 a truthful, $O(\log^3 n)$-approximate mechanism -\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-approximate mechanism for subadditive maximization +\cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate mechanism for subadditive maximization \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations) Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}. |