Approximability of the subset sum reconfiguration problem

DOI10.1007/S10878-012-9562-ZzbMATH Open1315.90036OpenAlexW1978916761MaRDI QIDQ489711FDOQ489711

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

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

zbMATH Keywords

approximation algorithmsubset sumPTASreachability on solution space

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• On the diameter of reconfiguration graphs for vertex colourings
• The complexity of rerouting shortest paths
• Approximability of the Subset Sum Reconfiguration Problem
• Games, puzzles, and computation
• Complexity of independent set reconfigurability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the complexity of reconfiguration problems
• Shortest paths between shortest paths
• Reconfiguration of list edge-colorings in a graph
• The Knapsack Problem with Conflict Graphs
• Title not available (Why is that?)
• On Bin Packing with Conflicts
• On the Boolean connectivity problem for Horn relations
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF

Cited In (9)

• 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
• 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 Q489711)