Institutional Repository
| a note on a selfish bin packing problem | |
| Ma Ruixin; D&#; sa Gy&#; rgy; Han Xin; Ting Hing-Fung; Ye Deshi; Zhang Yong | |
| 2012 | |
| Source | Journal of Global Optimization
 |
| ISSN | 0925-5001 |
| Pages | 1-6 |
| English 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.69103 OPT + 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(n2) steps without increasing the social cost. © 2012 Springer Science+Business Media, LLC.; 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.69103 OPT + 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(n2) steps without increasing the social cost. © 2012 Springer Science+Business Media, LLC. |
| Indexed Type | EI |
| Keyword | Bins Game Theory |
| Department | (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 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/15423 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Ma Ruixin,D&#,sa Gy&#,et al. a note on a selfish bin packing problem[J]. Journal of Global Optimization,2012:1-6. |
| APA | Ma Ruixin.,D&#.,sa Gy&#.,rgy.,Han Xin.,...&Zhang Yong.(2012).a note on a selfish bin packing problem.Journal of Global Optimization,1-6. |
| MLA | Ma Ruixin,et al."a note on a selfish bin packing problem".Journal of Global Optimization (2012):1-6. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment