a note on a selfish bin packing problem
文献类型：期刊论文
| 作者 | Ma Ruixin ; D&# ; sa Gy&# ; rgy ; Han Xin ; Ting Hing-Fung ; Ye Deshi ; Zhang Yong |
| 刊名 | Journal of Global Optimization
 |
| 出版日期 | 2012 |
| 页码 | 1-6 |
| 关键词 | Bins Game theory |
| ISSN号 | 0925-5001 |
| 中文摘要 | 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. |
| 收录类别 | EI |
| 语种 | 英语 |
| 公开日期 | 2013-09-17 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/15423]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。