A note on a selfish bin packing problem |
| |
Authors: | Ruixin Ma György Dósa Xin Han Hing-Fung Ting Deshi Ye Yong Zhang |
| |
Affiliation: | 1. School of Software, Dalian University of Technology, Dalian, China 2. Department of Mathematics, University of Pannonia, Veszprém, Hungary 3. Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong 4. College of Computer Science, Zhejiang University, Hangzhou, 310027, China 5. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Beijing, China
|
| |
Abstract: | In this paper, we consider a selfish bin packing problem, where each item is a selfish player and wants to minimize its cost. In our new model, if there are k items packed in the same bin, then each item pays a cost 1/k, where k ≥ 1. First we find a Nash Equilibrium (NE) in time O(n log n) within a social cost at most 1.69103OPT + 3, where OPT is the social cost of an optimal packing; where n is the number of items or players; then we give tight bounds for the worst NE on the social cost; finally we show that any feasible packing can be converged to a Nash Equilibrium in O(n 2) steps without increasing the social cost. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|