Approximability of the Subset Sum Reconfiguration Problem

DOI10.1007/978-3-642-20877-5_7zbMath1330.68094OpenAlexW1515923199MaRDI 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

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

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

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

This page was built for publication: Approximability of the Subset Sum Reconfiguration Problem