Approximability of the subset sum reconfiguration problem

DOI10.1007/S10878-012-9562-ZMaRDI QIDQ489711zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Erik D. Demaine

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 algorithmsubset sumPTASreachability on solution space

Mathematics Subject Classification ID

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

Recommendations

• Approximability of the Subset Sum Reconfiguration Problem
• A Fast Approximation Algorithm For The Subset-Sum Problem
• On the equal-subset-sum problem
• scientific article; zbMATH DE number 1104339

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• An exact algorithm for the Boolean connectivity problem for k-CNF
• Approximability of the Subset Sum Reconfiguration Problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of independent set reconfigurability problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Games, puzzles, and computation
• On Bin Packing with Conflicts
• On the Boolean connectivity problem for Horn relations
• On the complexity of reconfiguration problems
• On the diameter of reconfiguration graphs for vertex colourings
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration of list edge-colorings in a graph
• Relationships between nondeterministic and deterministic tape complexities
• Shortest paths between shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Knapsack Problem with Conflict Graphs
• The complexity of rerouting shortest paths

Cited in

(9)

• Approximability of the Subset Sum Reconfiguration Problem
• Independent set reconfiguration in cographs and their generalizations
• Using contracted solution graphs for solving reconfiguration problems
• On reconfigurability of target sets
• Reconfiguration of multisets with applications to bin packing
• A reconfigurations analogue of Brooks' theorem and its consequences
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• Reconfiguration of list \(L(2,1)\)-labelings in a graph

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489711)