Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952432 | Theoretical Computer Science | 2016 | 11 Pages |
Abstract
This paper aims to study techniques for designing truthful mechanisms for a combinatorial optimization problem that might require composition algorithms. We show that the composition algorithm AâB is monotone if the algorithm A and the algorithm B are both monotone. We apply this technique to the two-dimensional orthogonal knapsack problem with provable constant approximation bounds, improving the previous non-constant results in [5]. Moreover, we show that the technique can also be applied to the heterogeneous multiple clusters scheduling problem, and a truthful mechanism with provable approximation bounds was presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Deshi Ye, Guochuan Zhang,