The knapsack problem with neighbour constraints

DOI10.1016/j.jda.2012.04.011zbMath1262.90179OpenAlexW2034207294MaRDI QIDQ1932367

Glencora Borradaile, Brent Heeringa, Gordon Wilfong

Publication date: 18 January 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.011

zbMATH Keywords

approximation algorithmknapsack

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

The knapsack problem with special neighbor constraints ⋮ Subset sum problems with digraph constraints ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Precedence-Constrained Min Sum Set Cover

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-based facets for the precedence constrained knapsack problem
• Partially ordered knapsack and applications to scheduling
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• A threshold of ln n for approximating set cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Non-monotone submodular maximization under matroid and knapsack constraints

This page was built for publication: The knapsack problem with neighbour constraints