-
49浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
Maximizing the minimum load: The cost of selfishness
Theoretical Computer Science,2013,482():9-19 | 2013年04月22日 | https://doi.org/10.1016/j.tcs.2013.02.033
We consider a scheduling problem on machines, where each job is controlled by a selfish agent. Each agent is only interested in minimizing its own cost, defined as the total load of the machine that its job is assigned to. We consider the objective of maximizing the minimum load (the value of the cover) over the machines. Unlike the regular makespan minimization problem, which was extensively studied in a game-theoretic context, this problem has not been considered in this setting before. We study the price of anarchy (poa) and the price of stability (pos). These measures are unbounded already for two uniformly related machines [11], and therefore we focus on identical machines. We show that the is 1, and derive tight bounds on the pure for and on the overall pure , showing that its value is exactly 1.7. To achieve the upper bound of 1.7, we make an unusual use of weighting functions. Finally, we show that the mixed grows exponentially with for this problem. In addition, we consider a similar setting of selfish jobs with a different objective of minimizing the maximum ratio between the loads of any pair of machines in the schedule. We show that under this objective the is 1 and the pure is 2, for any .
【免责声明】以下全部内容由[陈旭瑾]上传于[2021年03月23日 11时07分18秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。
本学者其他成果
同领域成果