TY - GEN

T1 - Approximability of the subset sum reconfiguration problem

AU - Ito, Takehiro

AU - Demaine, Erik D.

PY - 2011

Y1 - 2011

N2 - 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 the 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.

AB - 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 the 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.

UR - http://www.scopus.com/inward/record.url?scp=79955786704&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955786704&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20877-5_7

DO - 10.1007/978-3-642-20877-5_7

M3 - Conference contribution

AN - SCOPUS:79955786704

SN - 9783642208768

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 58

EP - 69

BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings

T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011

Y2 - 23 May 2011 through 25 May 2011

ER -