Vi studerar en begränsad version av Knapsack problemet där beroenden mellan objekt ges av adjacensen av en graf. I problemet med 1-grannars knapsack kan ett objekt endast väljas om åtminstone en av grannarna också väljs. I problemet med alla grannars knapsack kan ett objekt endast väljas om alla grannar också väljs. Vi ger approximationsalgoritmer och hårdhetsresultat när noderna har både enhetliga och godtyckliga vikt- och vinstfunktioner, och när beroendekurvan är riktad och oriktad.
Två relaterade problem, kända som NEIGHBOUR KNAPSACK PROBLEM, studeras i REF där beroenden mellan objekt ges av en oriktad (eller en riktad) graf G = (V, E).
The Knapsack Problem with Neighbour Constraints
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}