Approximability of the subset sum reconfiguration problem

DOI10.1007/s10878-012-9562-zzbMath1315.90036OpenAlexW1978916761MaRDI QIDQ489711

Erik D. Demaine, Takehiro Ito

Publication date: 21 January 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9562-z

zbMATH Keywords

approximation algorithmPTASsubset sumreachability on solution space

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the Boolean connectivity problem for Horn relations
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The Complexity of Rerouting Shortest Paths
• Approximability of the Subset Sum Reconfiguration Problem
• The Knapsack Problem with Conflict Graphs
• On Bin Packing with Conflicts
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Approximability of the subset sum reconfiguration problem