diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-10 18:08:15 -0800 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-02-10 18:08:15 -0800 |
| commit | 91db9186fa25585c02a035e99386f73c75ad2601 (patch) | |
| tree | bb4bdae8683c9214400dff7d038d113b209ade0b /related.tex | |
| parent | 5bd3c3aef9533a2697c4b3660c53c1411fa18c77 (diff) | |
| download | recommendation-91db9186fa25585c02a035e99386f73c75ad2601.tar.gz | |
intro markets and typos
Diffstat (limited to 'related.tex')
| -rw-r--r-- | related.tex | 2 |
1 files changed, 1 insertions, 1 deletions
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 |