Was ist diese Variante des Set-Cover-Problems?

12

Eingang ist ein Universum und eine Familie von Untermengen von , sagen wir, . Wir gehen davon aus, daß die Teilmengen in abdecken können , dh .U F2 U F U E F E = UUUF2UFUEFE=U

Eine inkrementelle Überdeckungssequenz ist eine Folge von Teilmengen in , z. B. , die erfülltA = { E 1 , E 2 , ... , E | A | }FA={E1,E2,,E|A|}

1) ,EA,EF

2) jeder Neuling hat einen neuen Beitrag, dh , ;i - 1 j = 1 E ii j = 1 E ii>1j=1i1Eij=1iEi

Das Problem besteht darin, eine inkrementelle Überdeckungssequenz maximaler Länge zu finden (dh mit maximalem |A| ). Beachten Sie, dass eine Sequenz maximaler Länge schließlich bedecken muss U , dh EAE=U .

Ich habe versucht, einen Algorithmus oder einen Näherungsalgorithmus zu finden, um die längste inkrementelle Überdeckungssequenz zu finden. Ich habe mich nur gefragt, wie diese Variante des Set-Cover-Problems heißt. Vielen Dank!

Cech Cohomology
quelle
Sie benötigen Ihre Familie von Teilmengen , um das Universum abzudecken ? Denn dann können Sie natürlich ein schwierigeres Set-Cover-Problem haben, da Sie Set-Cover mit zusätzlichen Eigenschaften suchen. Mit anderen Worten, die Deckung reduziert sich auf Ihr Problem. Im Wiki von Set Cover sind auch die Unannäherungsergebnisse für Set Cover zu finden. UAU
Harry
1
Nur eine Beobachtung (zu klein, um eine Antwort zu geben): Wenn Ihre Teilmengen die Größe zwei haben, dann ist das, was Sie suchen, im Wesentlichen ein übergreifender Wald.
David Eppstein
Wahrscheinlich nicht neu für das OP, aber hier sind einige Beobachtungen. (1) Der optimale Wert ist immer höchstens | U |. Ob der optimale Wert gleich | U | ist oder nicht kann effizient durch den gierigen Algorithmus entschieden werden, der versucht, die Anzahl der abgedeckten Elemente zu minimieren. (2) Der gleiche Greedy-Algorithmus funktioniert auch, wenn alle Mengen in F die Größe zwei haben, siehe David Eppsteins Kommentar. (3) Derselbe Greedy-Algorithmus funktioniert im Allgemeinen nicht (Seufzer). Ein Gegenbeispiel: F = {{1,2,3}, {1,4,5,6}, {2,4,5,6}, {3,4,5,6}}.
Tsuyoshi Ito
1
Das Problem sieht nicht wirklich wie ein Set-Cover-Problem aus ... Eher wie eine Mischung aus Matching und induziertem Matching in zweigeteilten Graphen. Eine schöne äquivalente Neuformulierung ist, dass eine Familie schlecht ist, wenn kein Element von genau einer Menge in der Familie abgedeckt wird. Das Problem besteht darin, eine größte Unterfamilie von , sodass keine schlechte Unterfamilie hat. F AAFA
Daniello
1
@Neal Young ist nicht schlecht, weil von genau einer Menge abgedeckt wird (nämlich ). b { a , b }Fb{a,b}
Daniello

Antworten:

4

Hier zeige ich, dass das Problem NP-vollständig ist.

Wir konvertieren einen CNF wie folgt in eine Instanz Ihres Problems. Angenommen, die Variablen des CNF sind und die Klauseln sind , wobei . Es sei wobei alle Mengen in der Vereinigung vollständig disjunkt sind. Tatsächlich ist und , während eine beliebige Menge von Kardinalitäten . bezeichne auch und für jedes eine wachsende Familie der Länge darin fest, die mit für bezeichnet istx i m C j n < m U = i ( A iB iZ i ) A i = { a i , j | x iC j } { a i , 0 } B i = { b i , jx iC j } n xim Cjn<mU=i(AiBiZi)Ai={ai,jxiCj}{ai,0}Z i k = 2 n + 1 Z = i Z i Z i k Z i , l l = 1 .. k x i 2 k F A iZ i , l B iZ i , l C j F Z x iC j { aBi={bi,jxiCj}{bi,0}Zik=2n+1Z=iZiZikZi,ll=1..k . Für jede Variable addieren wir Mengen zu , jede Menge der Form und . Für jede Klausel fügen wir eine Menge zu , die enthält , und für jedes Element und für jeden Element .xi2kFAiZi,lBiZi,lCjFZxiCj{ai,j}x¯iCj{bi,j}

Angenommen, die Formel ist erfüllbar, und Sie legen eine erfüllende Zuordnung fest. Wählen Sie dann die Mengen der Form oder , je nachdem, ob wahr ist oder nicht. Dies sind inkrementelle Mengen. Fügen Sie nun die Mengen hinzu, die den Klauseln entsprechen. Diese vergrößern sich auch immer weiter, da die Klauseln befriedigend sind. Schließlich können wir noch weitere Mengen hinzufügen (eine für jede Variable), damit die Sequenz abdeckt .kAiZi,lBiZi,lxinkmkU

Nehmen wir nun an, dass Mengen in einer inkrementellen Reihenfolge gesetzt werden. Beachten Sie, dass höchstens Mengen, die entsprechen, für jedes ausgewählt werden können . Wenn also in der inkrementellen Sequenz keine Klauselsätze vorhanden sind, kann höchstens ausgewählt werden, was zu wenig ist. Beachten Sie, dass wir, sobald eine Klauselmenge ausgewählt ist, höchstens zwei Mengen entsprechend jedem auswählen können , insgesamt höchstens Mengen. Daher müssen wir mindestens Variablensätze auswählen, bevor ein Satz von Klauseln ausgewählt wird. Aber da wir höchstens für jedes x i auswählen könnenk + 1 x i x i n ( k + 1 ) x i 2 n n ( k - 1 ) k + 1n(k+1)+mk+1xixin(k+1)xi2nn(k1)k+1xiDies bedeutet, dass wir für jedes mindestens , als k = 2 n + 1 . Dies bestimmt den "Wert" der Variablen, daher können wir nur "wahre" Klauseln auswählen.1k=2n+1

Update: Der Wert von von n auf 2 n + 1 geändert, wie von Marzio herausgestellt.kn2n+1

domotorp
quelle
1
Eine Klarstellung: Ich habe die Konstruktion schnell auf die nicht erfüllbare Formel überprüft ( n = k = 1 , m = 2 ), aber es scheint, dass wir eine Folge von n ( k + 1 ) + m = 4 von bilden können Erhöhen Sätze von F . Wahrscheinlich mache ich einen Fehler: Haben wir F = { { a 1 , 0 , a 1 , 1 , a 1x1¬x1n=k=1,m=2n(k+1)+m=4F? F={{a1,0,a1,1,a1,2,z1},{b1,0,b1,1,b1,2,z1},{a1,1,z1},{b1,2,z1}}
Marzio De Biasi
Wenn ich Sie und mich kenne, bin ich sicher, dass der Fehler bei mir liegt ... Ich denke, wir sollten F={{a1,0,a1,1,z1},{b1,0,b1,2,z1},{a1,1,z1},{b1,2,z1}}Aber natürlich ist es immer noch ein Problem. OK, ich sehe, wo ich den Fehler gemacht habe, ich behebe ihn in einer Minute, danke!
Domotorp
Ok, ich schaue es mir morgen an! Nur eine Anmerkung, können Sie (in einem Kommentar) schreiben, was für x i¬ x i ist und was der "Zielwert" für die Länge der Deckungssequenz ist (ist es k)? Weil Sie in der modifizierten Antwort zuerst k = 2 n + 1 setzen und dann über n ( k + 1 ) + m = 2 n 2 + 2 n + m sprechen . ist es richtig (ich habe die Reduktion noch nicht ausprobiert)?Fxi¬xik=2n+1n(k+1)+m=2n2+2n+m
Marzio De Biasi
F={{a1,0,a1,1,z1,},{a1,0,a1,1,z1,z2},{a1,0,a1,1,z1,z2,z3},{b1,0,b1,2,z1},{b1,0,b1,2,z1,z2},{b1,0,b1,2,z1,z2,z3},{a1,1,z1,z2,z3},{b1,2,z1,z2,z3}}
domotorp
Ich denke, dies ist richtig als , aber wir haben nur Länge 5 inkrementelle Sequenzen. n(k+1)+m=65
Domotorp
0

Dies ist ein Mengenpackungsproblem unter der Bedingung, dass es für die Lösung für jede Teilmenge BA immer ein Element in X B X gibt , das genau einmal behandelt wird.ABAXBX

Beweis: Wenn Sie eine Lösung für Ihr Problem gefunden haben, hat es sofort diese Eigenschaft. In der Tat, wenn die optimale Lösung für Ihr Problem ist, dann betrachten Sie eine Teilmenge B dieser Mengen und nehmen an, dass E i die letzte Menge in dieser Sequenz ist, die in B vorkommt . Durch die erforderliche Eigenschaft, dass die Lösung inkrementell ist, folgt, dass E i ein Element abdeckt, das keine vorherige Menge abdeckt, was die obige Eigenschaft impliziert.E1,,EmBEiBEi

Was die andere Richtung betrifft, ist es auch einfach. Gehen Sie von Lösung , suchen Sie das Element, das genau einmal abgedeckt ist, stellen Sie es als letzten Satz in der Sequenz ein, entfernen Sie diesen Satz und wiederholen Sie den Vorgang. QED.A


Das ist ein ziemlich natürliches Problem ...


Schnelle Erinnerung: Finden Sie in dem Problem mit dem Packen von Sätzen bei einer gegebenen Familie von Sätzen die maximale Teilmenge von Sätzen, die einer zusätzlichen Einschränkung entsprechen (z. B. wird kein Element mehr als zehnmal abgedeckt usw.).

Sariel Har-Peled
quelle
Beweist diese Antwort nur, dass die Frage natürlich ist, oder gibt es noch etwas, das Sie auch behaupten?
Domotorp
Es sagt es auf einfachere Weise aus. Nein?
Sariel Har-Peled
Ja, dem stimme ich zu.
Domotorp