Approximability of the Subset Sum Reconfiguration Problem

DOI10.1007/978-3-642-20877-5_7zbMath1330.68094MaRDI QIDQ3010386

Erik D. Demaine, Takehiro Ito

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_7

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Finding shortest paths between graph colourings, Reconfiguration of dominating sets, Approximability of the subset sum reconfiguration problem, Reconfiguration on nowhere dense graph classes, Finding Shortest Paths Between Graph Colourings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• 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
• The Knapsack Problem with Conflict Graphs
• On Bin Packing with Conflicts
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies