Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms
We provide polynomial-time approximately optimal Bayesian mechanisms for makespan minimization on unrelated machines as well as for max-min fair allocations of indivisible goods, with approximation factors of 2 and min{m - k + 1, [~ over O](√k)} respectively, matching the approximation ratios of bes...
| Huvudupphovsmän: | , |
|---|---|
| Övriga upphovsmän: | |
| Materialtyp: | Artikel |
| Språk: | en_US |
| Publicerad: |
Society for Industrial and Applied Mathematics
2015
|
| Länkar: | http://hdl.handle.net/1721.1/99972 https://orcid.org/0000-0002-5451-0490 |