Paper by Erik D. Demaine

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.

BibTeX

@Article{SubsetSumReconfiguration_JOCO,
  AUTHOR        = {Takehiro Ito and Erik D. Demaine},
  TITLE         = {Approximability of the Subset Sum Reconfiguration Problem},
  JOURNAL       = {Journal of Combinatorial Optimization},
  journalurl    = {http://www.springerlink.com/content/102924/},
  VOLUME        = 28,
  NUMBER        = 3,
  MONTH         = {October},
  YEAR          = 2014,
  PAGES         = {639--654},

  length        = {14 pages},
  papers        = {SubsetSumReconfiguration_TAMC2011; NPReconfiguration_TCS; NPReconfiguration_WADS2009; NPReconfiguration_ISAAC2008},
  replaces      = {SubsetSumReconfiguration_TAMC2011},
  updates       = {Unfortunately Theorem 1 and Corollary 1 are flawed.
                   However, dropping the word “strongly”,
                   the results still hold.  Read
                   <A HREF="erratum.pdf">our erratum</A>.},
  doi           = {https://dx.doi.org/10.1007/s10878-012-9562-z},
  dblp          = {https://dblp.org/rec/journals/jco/ItoD14},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s10878-012-9562-z">SpringerLink</A>.},
}

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)