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
Last updated February 10, 2020 by