The Knapsack Problem with Neighbour Constraints

Details The Knapsack Problem with Neighbour Constraints The Knapsack Problem with Neighbour Constraints

2009-10-05

arxiv.org/abs/0910.0777v4

Computer Science

Data Structures and Algorithms

Full version of IWOCA 2011 paper

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Knapsack Problem with Neighbour Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Knapsack Problem with Neighbour Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Knapsack Problem with Neighbour Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-10144