Approximability of the subset sum reconfiguration problem
From MaRDI portal
Publication:489711
DOI10.1007/s10878-012-9562-zzbMath1315.90036MaRDI QIDQ489711
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
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Linear-time algorithm for sliding tokens on trees, On reconfigurability of target sets, Reconfiguration of list \(L(2,1)\)-labelings in a graph, Using contracted solution graphs for solving reconfiguration problems, Introduction to reconfiguration, Independent Set Reconfiguration in Cographs and their Generalizations, A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- On the Boolean connectivity problem for Horn relations
- On the complexity of reconfiguration problems
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- 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
- The Complexity of Rerouting Shortest Paths
- Approximability of the Subset Sum Reconfiguration Problem
- The Knapsack Problem with Conflict Graphs
- On Bin Packing with Conflicts
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
