两台自私型机器上自私工件排序的PoA紧界（英文）

作者：成夏炎; 何滢; 赵聪聪; 李荣珩^*

来源：运筹学学报, 2022, 26(03): 109-119.

DOI：10.15960/j.cnki.issn.1007-6093.2022.03.008

• 自私型机器
• 排序
• 紧界
• 纳什均衡

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列L,证明了二元均衡排序的PoA的紧界为8/7。如果工件尺寸在区间[1,r](r≥1)内,得到了二元均衡排序的PoA的紧界为关于r的分段线性函数。

• 单位
  湖南师范大学; 湖南第一师范学院