Approximability of the subset sum reconfiguration problem
Approximability of the subset sum reconfiguration problem
复制标题
DOI：
10.1007/s10878-012-9562-z
复制
发表时间：
2011-05
影响因子：
1
通讯作者：
Takehiro Ito;E. Demaine
中科院分区：
文献类型：
--
作者：
Takehiro Ito;E. Demaine
子集和问题是一个众所周知的 NP 完全问题，其中我们希望找到将物品（整数）打包（子集）到具有容量的背包中，使得打包中的整数之和最多为背包的容量且至少为给定的整数阈值。在本文中，我们研究了通过一次仅移动一件物品将一种包装重新配置为另一种包装的问题，同时始终保持包装的可行性。首先，我们证明这个决策问题是强 NP 困难的，并且如果我们给定一个项目集的冲突图，其中每个顶点对应一个项目，并且每条边代表一对不允许一起打包到背包中的项目，那么这个决策问题就是 PSPACE 完全的。然后我们研究该问题的优化版本：我们希望在重新配置中最大化所有包装中的最小总和。我们证明这个最大化问题承认多项式时间近似方案，而如果给定一个冲突图，则该问题是 APX 困难的。
Thesubset sumproblem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of the integers in the packing is at most the capacity of the knapsack and at least a given integer threshold. In this paper, we study the problem of reconfiguring one packing into another packing by moving only one item at a time, while at all times maintaining the feasibility of packings. First we show that this decision problem is strongly NP-hard, and is PSPACE-complete if we are given a conflict graph for the set of items in which each vertex corresponds to an item and each edge represents a pair of items that are not allowed to be packed together into the knapsack. We then study an optimization version of the problem: we wish to maximize the minimum sum among all packings in a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, while the problem is APX-hard if we are given a conflict graph.