点击次数：
论文类型：期刊论文
发表时间：2013-08-01
发表刊物：8th International Tri-Annual Conference on Optimization - Techniques and Applications (ICOTA)
收录刊物：SCIE、EI、CPCI-S、Scopus
卷号：56
期号：4,SI
页面范围：1457-1462
ISSN号：0925-5001
关键字：Equilibrium; Bin packing; Approximation ratio
摘要：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 a parts per thousand yen 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.