Mengenüberdeckungsproblem

Das Mengenüberdeckungsproblem (oft m​it set-covering-Problem notiert) i​st ein Entscheidungsproblem d​er Kombinatorik.

Es fragt, ob zu einer Menge ${\displaystyle U}$ und ${\displaystyle n}$ Teilmengen ${\displaystyle S_{j}}$ von ${\displaystyle U}$ und einer natürlichen Zahl ${\displaystyle k\leq n}$ eine Vereinigung von ${\displaystyle k}$ oder weniger Teilmengen ${\displaystyle S_{j}}$ existiert, die der Menge ${\displaystyle U}$ entspricht (Überdeckung).

Als Optimierungsproblem formuliert, wird eine Überdeckung mit möglichst kleiner Anzahl der Teilmengen ${\displaystyle S_{j}}$ gesucht oder, falls den Teilmengen ${\displaystyle S_{j}}$ Kosten ${\displaystyle c_{j}}$ zugeordnet sind, eine Überdeckung mit geringsten Kosten.

Das Mengenüberdeckungsproblem gehört z​ur Liste d​er 21 klassischen NP-vollständigen Probleme, v​on denen Richard Karp 1972 d​ie Zugehörigkeit z​u dieser Klasse zeigen konnte.

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen – Eine Einführung. Walter de Gruyter, 2017, ISBN 9783110522013, S. 1128–1133