Approximability of the subset sum reconfiguration problem
type: Item
instance of: scholarly article
title: Approximability of the subset sum reconfiguration problem
zbMATH Open document ID: 1315.90036
author: Takehiro Ito
author: Erik D. Demaine
published in: Journal of Combinatorial Optimization
publication date: 2015-01-21T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6388489
zbMATH Keywords: approximation algorithm
zbMATH Keywords: PTAS
zbMATH Keywords: reachability on solution space
zbMATH Keywords: subset sum
MaRDI profile type: Publication
full work available at URL: s10878-012-9562-z
OpenAlex ID: W1978916761
cites work: Q4260373
cites work: On the diameter of reconfiguration graphs for vertex colourings
cites work: The Complexity of Rerouting Shortest Paths
cites work: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
cites work: On Bin Packing with Conflicts
cites work: Q4198056
cites work: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
cites work: Q3395518
cites work: Approximability of the Subset Sum Reconfiguration Problem
cites work: On the complexity of reconfiguration problems
cites work: Reconfiguration of list edge-colorings in a graph
cites work: Shortest paths between shortest paths
cites work: Complexity of independent set reconfigurability problems
cites work: Q4821303
cites work: On the Boolean connectivity problem for Horn relations
cites work: An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
cites work: Q4298260
cites work: The Knapsack Problem with Conflict Graphs
cites work: Relationships between nondeterministic and deterministic tape complexities
DOI: 10.1007/S10878-012-9562-Z
description: scientific article; zbMATH DE number 6388489