Cost-Sharing Mechanisms for Selfish Bin Packing

被引：4

作者：

Zhang, Chenhao ^{[1
]}

Zhang, Guochuan ^{[1
]}

机构：

[1] Zhejiang Univ, Coll Comp Sci, Hangzhou, Peoples R China

来源：

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I | 2017年 / 10627卷

关键词：

D O I：

10.1007/978-3-319-71150-8_30

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The selfish bin packing problem (SBP) considers the classical bin packing problem in a game-theoretic setting where each item is controlled by a selfish agent. It is well-known that the classical bin packing problem admits an asymptotic fully polynomial-time approximation scheme (AFPTAS). However, all previously-studied cost-sharing mechanisms for the selfish bin packing problem (SBP) have PoA greater than 1.6. Obviously, there is quite a big gap between the results of the two highly-related problems. In this paper, we revisit the SBP and find more efficient mechanisms for SBP to narrow the gap. We first present a simple mechanism with PoA = 1.5, which significantly improves previous bounds. We observe that for a large class of mechanisms for the SBP, 1.5 is actually a lower bound of PoA. Finally, we propose new rules for the SBP which lead a better mechanism with PoA <= 1.467.

引用

页码：355 / 368

页数：14

共 12 条

[1] Selfish bin packing with cardinality constraints
Adar, Ron
Epstein, Leah
[J]. THEORETICAL COMPUTER SCIENCE, 2013, 495 : 66 - 80
[2] Bilo V., 2006, P 20 INT PAR DISTR P
[3] Selfish bin covering
Cao, Zhigang
Yang, Xiaoguang
[J]. THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) : 7049 - 7058
[4] Chan T.-H.H., 2016, LNCS, V10043, P46, DOI [10.1007/978-3-319-48749-6, DOI 10.1007/978-3-319-48749-646]
[5] DELAVEGA WF, 1981, COMBINATORICA, V1, P349
[6] Epstein L, 2008, LECT NOTES COMPUT SC, V5193, P368, DOI 10.1007/978-3-540-87744-8_31
[7] Epstein L, 2009, LECT NOTES COMPUT SC, V5929, P67, DOI 10.1007/978-3-642-10841-9_8
[8] Johnson D. S., 1974, SIAM Journal on Computing, V3, P299, DOI 10.1137/0203025
[9] Koutsoupias E, 1999, LECT NOTES COMPUT SC, V1563, P404
[10] A note on a selfish bin packing problem
Ma, Ruixin
Dosa, Gyoergy
Han, Xin
Ting, Hing-Fung
Ye, Deshi
Zhang, Yong
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 2013, 56 (04) : 1457 - 1462

← 1 2 →