期刊
THEORY OF COMPUTING SYSTEMS
卷 63, 期 1, 页码 114-127出版社
SPRINGER
DOI: 10.1007/s00224-018-9857-2
关键词
Coordination mechanisms; Potential games; Price of anarchy; Price of stability; Scheduling; Unrelated machines
资金
- Caratheodory grant from the University of Patras [E.114]
- project CoCoRICo-CoDec [ANR-14-CE24-0007-01]
Coordination mechanisms aim to mitigate the impact of selfishness when scheduling jobs to different machines. Such a mechanism defines a scheduling policy within each machine and naturally induces a game among the selfish job owners. The desirable properties of a coordination mechanism includes simplicity in its definition and efficiency of the outcomes of the induced game. We present a broad class of coordination mechanisms for unrelated machine scheduling that are simple to define and we identify one of its members (mechanism DCOORD) that is superior to all known mechanisms. In particular, DCOORD induces potential games with logarithmic price of anarchy and only constant price of stability. Both bounds are almost optimal.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据