Paper by Erik D. Demaine

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.

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.

This paper is also available from SpringerLink.

Unfortunately Theorem 1 and Corollary 1 are flawed. However, dropping the word “strongly”, the results still hold. Read our erratum.

The paper is 14 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated July 23, 2024 by Erik Demaine.