Glencora Borradaile

Glencora Borradaile, Brent Heeringa, Gordon Wilfong

We study constrained versions of the knapsack problem in which dependencies between items are given by a graph. In one version, an item can be selected only if one of its neighbours is also selected. In the other version, an item can be selected only when all its neighbours are also selected. These problems generalize and unify several problems including the prize collecting and budgeted maximum coverage problems. 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.

[ arXiv ]

Filed under: Other, Publications by Glencora