2009/10/05 by Glencora Borradaile, Borradaile, Glencora, Brent Heeringa +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0910.0777
Full version of IWOCA 2011 paper
openalex publication_date 2009/10/05 · arxiv created 2011/09/27 · arxiv updated 2011/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.