Problem ähnlich wie beim Packen

7

Rufen Sie eine Familie von Sets an F={S1,,Sk} "vielfältig" wenn jeder Satz SiFhat mindestens ein eindeutiges Element. Was sind mögliche Ansätze, um die größte Vielfalt zu findenS in einer Familie von Sets F?

Ein Ansatz besteht darin, ein modifiziertes Packungsproblem zu lösen. AnnehmenF={S1,,Sk}. LassenK eine Teilmenge von Elementen sein, KSi, und lass FK={S1K,,SkK}. Dann die maximal vielfältige MengeS entspricht der größten maximal eingestellten Packung aus FL wo L ist die Menge aller nicht eindeutigen Elemente in F.

Aber was ist eine gute Heuristik für die Auswahl K? Oder gibt es insgesamt bessere Ansätze?

charles.y.zheng
quelle
Herzlich willkommen! Ist die Basismenge endlich?
Raphael
1
Beachten Sie, dass Sie nach einem minimalen Satz fragen S so dass das Ergebnis FSist eine Anti-Kette unter der Teilmengenbeziehung.
Nicholas Mancuso

Antworten:

2

Das Problem ist NP-vollständig. Dies schließt einen exakten Algorithmus aus, der unter allen Umständen funktioniert, schließt jedoch heuristische Algorithmen, die in der Praxis gut funktionieren, oder Approximationsalgorithmen mit nachweisbaren Approximationsgarantien nicht aus.

Die Ermäßigung beträgt 3SAT. Gegeben eine 3SAT-Instanzϕ mit Variablen x1,,xn und Klauseln ϕ1,,ϕmKonstruieren Sie das folgende Mengen-System. Für jede Variablexi Es gibt zwei Sätze Ai,0 und Ai,1 und N=n+1 setzt Bi,t={βi,t,0,βi,t,1}und für jede Klausel ϕj Es gibt einen Satz Cj={γj,1,γj,2,γj,3}. Der SatzAi,b besteht aus folgenden Elementen:

  • Das N+1 Elemente αi,βi,1,b,,βi,N,b.
  • Für jede Klausel ϕj das beinhaltet xi als die kth wörtlich und ist nicht zufrieden mitxi=b, das Element γj,k.

Man kann finden n(N+1)+m verschiedene Sets genau dann, wenn ϕist zufriedenstellend. In der Tat angesichts einer zufriedenstellenden Aufgabex, die Familie {Aixi:i[n]}{Bi,t:i[n],t[N]}{Cj:j[m]} ist vielfältig: αi gehört nur zu Aixi, βi,t,1xi gehört nur zu Bi,tund wenn die kth wörtlich von ϕj ist dann zufrieden γj,k gehört nur zu Cj.

Für das Gegenteil, nehmen wir an S=ABC ist zumindest eine vielfältige Familie von Größe n(N+1)+m, partitioniert nach dem Typ des Sets. WennA enthält beides Ai,0 und Ai,1 für einige i, dann Bi,1,,Bi,NB. Daher|S|2n+(n1)N+m<n(N+1)+m, was unmöglich ist. DeshalbB und C muss alle Sätze des entsprechenden Typs enthalten, und A muss enthalten n Mengen, die zusammen eine Zuordnung codieren x. Schon seitCjS ist vielfältig, konstruktionsbedingt die Zuordnung x erfüllt Klausel ϕjdaher ϕ ist zufriedenstellend.

Yuval Filmus
quelle