2013/06/17 by Xujin Chen, Chen, Xujin, Donglei Du +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1306.3909
openalex publication_date 2013/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We design a Copula-based generic randomized truthful mechanism for scheduling on two unrelated machines with approximation ratio within [1.5852, 1.58606], offering an improved upper bound for the two-machine case. Moreover, we provide an upper bound 1.5067711 for the two-machine two-task case, which is almost tight in view of the lower bound of 1.506 for the scale-free truthful mechanisms [4]. Of independent interest is the explicit incorporation of the concept of Copula in the design and analysis of the proposed approximation algorithm. We hope that techniques like this one will also prove useful in solving other problems in the future.