4.3 Article

Selfish bin packing with punishment

期刊

THEORETICAL COMPUTER SCIENCE
卷 982, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.tcs.2023.114276

关键词

Combinatorial optimization; Selfish bin packing; Punishment; Price of Anarchy; Nash equlibrium

向作者/读者索取更多资源

This paper studies the problem of selfish bin packing with punishment. Different types of punishments are considered, and it is shown that punishment based on the result can achieve better performance with an upper bound of approximately 1.48 compared to the optimal solution.
In this paper we study the problem of selfish bin packing with punishment. Different from the selfish bin packing problem proposed by Bila in 2006, where the items are astute to minimize their shared proportional cost in a bin, we consider the case that items are into the utility defined as the load of bin it is packed in and, a unilateral moving may incur punishment. We define and consider several kinds of punishment, which can be roughly classified into two types: the punishment according to the behavior and the punishment based on the result. For both types we present the tight bound for Price of Anarchy (PoA) under the objective of minimizing the number of bins used. The results proved show that punishment does not always work, a punishment based on the result can be viewed as a delicate designed threat in advance which could perform much better, with an approximate 1.48 upper bound comparing to the optimal solution.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据