**Reference**:- Takehiro Ito and Erik D. Demaine, “Approximability of the Subset Sum Reconfiguration Problem”,
*Journal of Combinatorial Optimization*, volume 28, number 3, October 2014, pages 639–654. **Abstract**:- The subset sum problem 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 (PTAS), while the problem is APX-hard if we are given a conflict graph.
**Comments**:- This paper is also available from SpringerLink.
**Updates**:- Unfortunately Theorem 1 and Corollary 1 are flawed. However, dropping the word “strongly”, the results still hold. Read our erratum.
**Length**:- The paper is 14 pages.
**Availability**:- The paper is available in PostScript (2252k), gzipped PostScript (1082k), and PDF (222k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- SubsetSumReconfiguration_TAMC2011 (Approximability of the Subset Sum Reconfiguration Problem)
- NPReconfiguration_TCS (On the Complexity of Reconfiguration Problems)
- NPReconfiguration_WADS2009 (Reconfiguration of List Edge-Colorings in a Graph)
- NPReconfiguration_ISAAC2008 (On the Complexity of Reconfiguration Problems)

See also other papers by Erik Demaine.

Last updated March 12, 2024 by Erik Demaine.