Approximation Algorithms for Constrained Knapsack Problems
Explore this paper's citation graph
Summary
Constrained versions of the knapsack problem, in which dependencies between items are given by a graph, are studied, giving approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions.
- Type
- article
- Published
- 2009-01-01
- Cited by
- 4
- References
- 9
- OpenAlex
- https://openalex.org/W59554375
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:16616504
Keywords
Knapsack problem, Mathematics, Continuous knapsack problem, Mathematical optimization, Graph
References
- A threshold of ln n for approximating set cover (preliminary version)
- Partially ordered knapsack and applications to scheduling
- The Budgeted Maximum Coverage Problem
- On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
- Polylogarithmic inapproximability
- Approximation Algorithms
- The Minimum k-Colored Subgraph Problem in Haplotyping and DNA Primer Selection
- A threshold of ln n for approximating set cover
- Knapsack Problems
- Reducibility Among Combinatorial Problems
Cited by
- Conflict Resolution Strategies During Product Configuration
- Towards Bridging IoT and Cloud Services: Proposing Smartphones as Mobile and Autonomic Service Gateways
- Maximizing Submodular Set Function With Connectivity Constraint: Theory and Application to Networks
- Maximizing Submodular Set Function With Connectivity Constraint: Theory and Application to Networks
- The 1-Neighbour Knapsack Problem
Related papers
- The knapsack problem with neighbour constraints
- Approximation Algorithms for the Generalized Multiple Knapsack Problems with K Restricted Elements
- New polynomial-time instances to various knapsack-type problems
- Approximation algorithms for the generalized incremental knapsack problem
- Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem
- A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
- The average behaviour of greedy algorithms for the knapsack problem: General distributions