a note on a selfish bin packing problem

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
ISSN	0925-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(n²) 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(n²) 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.