The knapsack problem with special neighbor constraints

Artikel

The knapsack problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two knapsack problems which contain additional constraints in the form of directed graphs whose vertex set corresponds to the item set. In the one-neighbor knapsack problem, an item can be chosen only if at least one of its neighbors is chosen. In the all-neighbors knapsack problem, an item can be chosen only if all its neighbors are chosen. For both problems, we consider uniform and general profits and weights. We prove upper bounds for the time complexity of these problems when restricting the graph constraints to special sets of digraphs. We discuss directed co-graphs, minimal series-parallel digraphs, and directed trees.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: Mathematical Methods of Operations Research ; ISSN: 1432-5217 ; Volume: 95 ; Year: 2021 ; Issue: 1 ; Pages: 1-34 ; Berlin, Heidelberg: Springer

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Multiple or Simultaneous Equation Models; Multiple Variables: Other ; Mathematical Methods; Programming Models; Mathematical and Simulation Modeling: Other
• Thema: Knapsack problem ; Neighbor constraints ; Directed co-graphs ; Minimal series-parallel digraphs ; Directed trees

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Goebbels, Steffen ; Gurski, Frank ; Komander, Dominique
• Ereignis: Veröffentlichung
• (wer): Springer
• (wo): Berlin, Heidelberg
• (wann): 2021

Weitere Informationen

• DOI: doi:10.1007/s00186-021-00767-5
• Letzte Aktualisierung: 10.03.2025, 11:41 MEZ