ISCAS OpenIR
a note on a selfish bin packing problem
Ma Ruixin; D&#; sa Gy&#; rgy; Han Xin; Ting Hing-Fung; Ye Deshi; Zhang Yong
2012
发表期刊Journal of Global Optimization
ISSN0925-5001
页码1-6
摘要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
关键词Bins Game Theory
部门归属(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
语种英语
内容类型期刊论文
URI标识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.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Ma Ruixin]的文章
[D&#]的文章
[sa Gy&#]的文章
百度学术
百度学术中相似的文章
[Ma Ruixin]的文章
[D&#]的文章
[sa Gy&#]的文章
必应学术
必应学术中相似的文章
[Ma Ruixin]的文章
[D&#]的文章
[sa Gy&#]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。