OREGON STATE UNIVERSITY

You are here

The knapsack problem with neighbour constraints

TitleThe knapsack problem with neighbour constraints
Publication TypeJournal Article
Year of Publication2012
AuthorsBorradaile, G., B. Heeringa, and G. Wilfong
JournalJournal of Discrete Algorithms
Volume16
Pagination224 - 235
Date Published10/2012
ISSN15708667
Keywordsapproximation algorithm, knapsack
Abstract

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 vertices have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.

DOI10.1016/j.jda.2012.04.011
Short TitleJournal of Discrete Algorithms