Ich möchte das Problem unten aus einem Lehrbuch lese ich lese, aber ich bin mir nicht sicher, wie es geht. In der Tat bin ich nicht sicher, ob es überhaupt richtig ist, da ich denke, dass wir die maximale Häufigkeit eines Elements in den Mengen und nicht die maximale Größe eines Satzes benötigen, einen Wert, den ich nicht verwenden kann, den ich mir vorstellen kann.Hitting Set Algorithmus Approximation
Wir haben eine Menge A = {a 1 ..... a n} und eine Sammlung von Teilmengen von A, sagen B 1, B 2, ..., B m. Jedes Element ai ∈ A hat ein Gewicht wi> 0. Das Problem besteht darin, eine Untermenge H ⊆ A zu finden, so dass das Gesamtgewicht der Elemente in H minimiert wird, und bei zur gleichen Zeit schneidet H alle Untermengen von Sammlung, dh H ∩ B i nicht ∅ für jedes i = 1, ..., m. Sei b = max i | B i | die maximale Größe der Teilmengen B 1, B 2, ..., B m sein. Geben Sie einen polynomiellen b-Approximationsalgorithmus für dieses Problem an.
'b * m' ist die Zeit, die es dauert, um durch jede Mitgliedschaft jedes Satzes zu iterieren, was Sie tun müssen, um beispielsweise die Häufigkeit von Elementen in den Mengen zu berechnen. Die Frage bleibt mir jedoch unklar. Was ist ihre Definition für "b-approximation algorithm"? Wenn sie Polynom sagen, meinen sie Polynom in m oder b? – btilly