This paper provides a technique for designing truthful mechanisms for a combinatorial optimization problem, which requires composition algorithms. We show that the composition algorithm A o B is monotone if the algorithm A and the algorithm B are both monotone. Then, we apply this technique to the two-dimensional orthogonal knapsack problem with provable approximation bounds, improving the previous results in.
展开▼
机译：本文提供了一种用于设计组合优化问题的真实机制的技术，该技术需要组合算法。我们证明，如果算法A和算法B都是单调的，则合成算法A o B是单调的。然后，我们将此技术应用于具有可证明的近似边界的二维正交背包问题，从而改善了先前的结果。
展开▼
