diff options
| author | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-06 14:05:17 -0700 |
|---|---|---|
| committer | Stratis Ioannidis <stratis@stratis-Latitude-E6320.(none)> | 2013-07-06 14:05:17 -0700 |
| commit | 411e59045922c4d50d14fb30aa5e0bdeecf42991 (patch) | |
| tree | ebd12ef1f4e0590d89bd1b5f0be55073a726a1c0 /abstract.tex | |
| parent | 17ab40af5d34a43ef07a9d310af07d29cce5853a (diff) | |
| download | recommendation-411e59045922c4d50d14fb30aa5e0bdeecf42991.tar.gz | |
intro sufficiently concave
Diffstat (limited to 'abstract.tex')
| -rw-r--r-- | abstract.tex | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/abstract.tex b/abstract.tex index d62c1d5..2f33699 100644 --- a/abstract.tex +++ b/abstract.tex @@ -19,6 +19,6 @@ Each subject $i$ declares an associated cost $c_i >0$ to be part of the experime mechanism for \SEDP{} with suitable properties. We present a deterministic, polynomial time, $\delta$-truthful, budget feasible mechanism for \SEDP{}. -By applying previous work on budget feasible mechanisms with submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to generalize our approach to a wide class of learning problems. +By applying previous work on budget feasible mechanisms with submodular objective, one could {\em only} have derived either an exponential time deterministic mechanism or a randomized polynomial time mechanism. Our mechanism yields a constant factor ($\approx 12.68$) approximation, and we show that no truthful, budget-feasible algorithms are possible within a factor $2$ approximation. We also show how to generalize our approach to a wide class of learning problems, beyond linear regression. |