Ich habe versucht, eine 3-Approximation für dieses Problem zu finden.

Meine erste Idee war, dass die optimale Lösung aus jeder Teilmenge in $F$ mindestens ein Element enthalten muss – also könnte man einfach alle Elemente aus $U$ auswählen und hätte damit eine 3-Approximation.

Das ist aber offensichtlich falsch, da ein einzelnes Element mehrere Mengen aus $F$ abdecken kann.

 

Eine weitere Idee war eine gierige (greedy) Variante: In jedem Schritt wählt man das Element aus $U$, das die meisten aktuell noch nicht abgedeckten Mengen aus F abdeckt. Danach entfernt man alle durch dieses Element abgedeckten Mengen aus $F$.

Diesen Prozess wiederholt man, bis $F$ leer ist.

Ich bin mir jedoch nicht sicher, ob dieses Verfahren wirklich eine 3-Approximation liefert – und wenn ja, wie man das beweisen könnte.