Approximability of the Subset Sum Reconfiguration Problem

DOI10.1007/978-3-642-20877-5_7MaRDI QIDQ3010386zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Erik D. Demaine

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

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

Recommendations

• Approximability of the subset sum reconfiguration problem
• scientific article; zbMATH DE number 1104339
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• scientific article; zbMATH DE number 1223719
• A Fast Approximation Algorithm For The Subset-Sum Problem
• A Fast Approximation Algorithm for the Subset-sum Problem
• Approximation schemes for subset sum ratio problems
• Efficient approximation algorithms for the subset-sums equality problem.
• A Structural Approach to Subset-Sum Problems
• Approximation schemes for subset-sums ratio problems

Cites work

• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• 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 1839431 (Why is no real title available?)
• On Bin Packing with Conflicts
• On the complexity of reconfiguration problems
• 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 Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Knapsack Problem with Conflict Graphs

Cited in

(4)

• Reconfiguration on nowhere dense graph classes
• Finding shortest paths between graph colourings
• Finding shortest paths between graph colourings
• Approximability of the subset sum reconfiguration problem

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 Q3010386)