TY - JOUR
T1 - Approximability of the subset sum reconfiguration problem
AU - Ito, Takehiro
AU - Demaine, Erik D.
N1 - Funding Information:
Acknowledgments We thank the referees for their helpful comments and suggestions. The first author’s work is partially supported by JSPS KAKENHI Grant No. 22700001. The second author’s work is supported in part by NSF Grant CCF-1161626 and DARPA/AFOSR Grant FA9550-12-1-0423.
PY - 2014/10
Y1 - 2014/10
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 a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, 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 a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, while the problem is APX-hard if we are given a conflict graph.
KW - Approximation algorithm
KW - PTAS
KW - Reachability on solution space
KW - Subset sum
UR - http://www.scopus.com/inward/record.url?scp=84906949122&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906949122&partnerID=8YFLogxK
U2 - 10.1007/s10878-012-9562-z
DO - 10.1007/s10878-012-9562-z
M3 - Article
AN - SCOPUS:84906949122
SN - 1382-6905
VL - 28
SP - 639
EP - 654
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -