.png){kind=icon}
返回
The Subset Sum game
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2013.08.047.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left. We look at the problem from a single agent point of view and show that finding an optimal sequence of items to select is NP-hard problem. Therefore we propose two natural heuristic strategies and analyze their worst-case performance when (1) the opponent is able to play optimally and (2) the opponent adopts a greedy strategy. From a centralized perspective we observe that some known results on the approximation of the classical Subset Sum can be effectively adapted to the multi-agent version of the problem. (C) 2013 The Authors. Published by Elsevier B.V. All rights reserved.
Keyword:
Subset Sum problem
Multi-agent optimization
Performance analysis
Game theory
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
Vitamin D status and acute lower respiratory infection in early childhood in Sylhet, Bangladesh
PREAI
分享收藏分享收藏Optimization of Process Parameters in Submerged Arc Welding Using Multi-objectives Taguchi Method
PREAI
分享收藏
查看更多内容