EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The knapsack problem with special neighbor constraints

Steffen Goebbels, Frank Gurski, Dominique Komander

Mathematical Methods of Operations Research · 2022-02 · 95 (1) · 1-34

DOI: 10.1007/s00186-021-00767-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Methods of Operations Research, online erschienen am 28.12.2021. Verfasst von Steffen Goebbels und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Heinrich-Heine-Universität Düsseldorf.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Heinrich-Heine-Universität Düsseldorf

Zitieren

APA

Goebbels, S., Gurski, F., & Komander, D. (2022). The knapsack problem with special neighbor constraints. Mathematical Methods of Operations Research, 95(1), 1-34. https://doi.org/10.1007/s00186-021-00767-5

Vancouver

Goebbels S, Gurski F, Komander D. The knapsack problem with special neighbor constraints. Mathematical Methods of Operations Research. 2022;95(1):1-34. doi:10.1007/s00186-021-00767-5

BibTeX
@article{Goebbels2022,
  author = {Goebbels, Steffen and Gurski, Frank and Komander, Dominique},
  title = {The knapsack problem with special neighbor constraints},
  journal = {Mathematical Methods of Operations Research},
  year = {2022},
  volume = {95},
  number = {1},
  pages = {1--34},
  doi = {10.1007/s00186-021-00767-5}
}
Kostenlos starten →