A Unified Approach to Truthful Scheduling on Related Machines

• 成果类型: Article
• 署名作者: Epstein, Leah; Levin, Asaf; van Stee, Rob
• 署名单位: University of Haifa; Technion Israel Institute of Technology; University of Leicester
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0730
• 发表日期: 2016
• 页码: 332-351
• 关键词: approximation schemes; algorithms; mechanisms; bounds; load

摘要

We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. Our results imply the existence of a truthful mechanism that can be implemented in polynomial time, where the social goal is approximated within arbitrary precision.