Paper by Erik D. Demaine

Reference:

Takehiro Ito and Erik D. Demaine, “Approximability of the Subset Sum Reconfiguration Problem”, in Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Lecture Notes in Computer Science, volume 6648, Tokyo, Japan, May 23–25, 2011, pages 58–69.

BibTeX

@InProceedings{SubsetSumReconfiguration_TAMC2011,
  AUTHOR        = {Takehiro Ito and Erik D. Demaine},
  TITLE         = {Approximability of the Subset Sum Reconfiguration Problem},
  BOOKTITLE     = {Proceedings of the 8th Annual Conference on Theory and
                   Applications of Models of Computation (TAMC 2011)},
  ADDRESS       = {Tokyo, Japan},
  MONTH         = {May 23--25},
  YEAR          = 2011,
  PAGES         = {58--69},
  SERIES        = {Lecture Notes in Computer Science},
  VOLUME        = 6648,

  length        = {14 pages},
  papers        = {SubsetSumReconfiguration_JOCO; NPReconfiguration_TCS; NPReconfiguration_WADS2009; NPReconfiguration_ISAAC2008},
  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/978-3-642-20877-5_7},
  dblp          = {https://dblp.org/rec/conf/tamc/ItoD11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-20877-5_7">SpringerLink</A>.},
}

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 PDF (392k).

See information on file formats.

[Google Scholar search]

Related papers:

SubsetSumReconfiguration_JOCO (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)