Wie partitioniere ich eine Menge unter bestimmten Bedingungen in eine bestimmte Anzahl disjunkter Teilmengen?

Ich eine Menge , eine ganze Zahl und nicht negative ganze Zahlen a_ {ij} . Mein Problem besteht darin, s disjunkte Teilmengen S_j von \ {1, \ ldots, k \} so zu finden, dass:s ⩽ k a i j s S j { 1 , … , k $A\triangleq\{1,\ldots,k\}$$s\leqslant k$$a_{ij}$$s$$S_j$$\{1,\ldots,k\}$

1. $\bigcup_{j=1}^s S_j=A$ ; und
2. $|S_j|\leqslant a_{ij}$ für alle $i\in S_j$ und $j=1,\ldots,s$ .

Wie kann man dieses Problem lösen? Ist es schwierig, eine praktikable Lösung zu finden?

Ich denke, es ist nicht einfach, das Problem zu lösen, weil ich eine Prozedur ausprobiert habe, die mit j \ in \ {1, \ ldots, n \} beginnt $j\in\{1,\ldots,n\}$und $i\in\{1,\ldots,k\}$ bis zur Nummer zuweist von $i$ zugewiesen $j$ größer als $a_{ij}$ für einige $i$ zugeordnet. Dies ist jedoch nicht korrekt, da ich von einigen i übrig bleiben $i$könnte, die keinem j zugewiesen werden könnten $j$(aufgrund ihres $a_{ij}$ das nicht erfüllt werden konnte).

Die Brute-Force-Methode, bei der ich alle Teilmengen von A generieren $A$und jede testen muss, funktioniert für mich ( $k=8,n=3$ ), ist aber sehr ineffizient.

Dieses Problem ist durch Reduzierung von Vertex Cover NP-schwer.

Im Vertex Cover-Problem erhalten wir einen Graphen und eine Zahl , und unsere Aufgabe besteht darin, zu bestimmen, ob es eine Teilmenge von höchstens Eckpunkten von so dass jede Kante in einfällt auf zumindest einen Scheitelpunkt in . (Entsprechend: Ist es möglich, jede Kante in zu töten, indem höchstens Eckpunkte gelöscht werden ?)r U r V E U G $G = (V, E)$$r$$U$$r$$V$$E$$U$$G$$r$

Zuerst Partitionieren in disjunkte Untermengen entspricht , jedes Element in der Zuweisung genau einer der möglichen Etiketten. Die Grundidee der Reduktion besteht darin, für jeden Scheitelpunkt in eine Beschriftung zu erstellen und jeder Kante nur eine der beiden Beschriftungen zu "erlauben", die ihren Endpunkten entsprechen, im folgenden Sinne: Zuweisen einer Kante eine entsprechende Mit label wird keine (echte) Einschränkung eingeführt, welche anderen Kanten derselben Beschriftung zugewiesen werden können, während durch Zuweisen einer Kante zu einer nicht entsprechenden Beschriftung verhindert wird, dass einer anderen Kante dieselbe Beschriftung zugewiesen wird - was natürlich dazu führt, dass die Nummer nach oben verschoben wird von verschiedenen Etiketten erforderlich.s A s S j v j$A$$s$$A$$s$$S_j$$v_j$$V$

So erstellen Sie eine Instanz Ihres Problems aus einer Instanz von Vertex Cover:( G , r $(A, a, s)$$(G, r)$

1. Setze aufUnd ein Element schaffen in für jede Kante in . (Diese Paare können als die ganzen Zahlen ; jede Bijektion zwischen ihnen reicht aus.)| E | ( i , j ) A v i v j E 1 , … , $k$$|E|$$(i, j)$$A$$v_iv_j$$E$$1, \dots, k$
2. Setze aufwenn oder ; Andernfalls setzen Sie auf 1. | E | d = b d = c a ( b , c ) , $a_{(b, c), d}$$|E|$$d=b$$d=c$$a_{(b, c), d}$
3. Setze .$s=r$

WennS j v j U v b v c ∈ E ( b , c ) ∈ A S b S c s a i j | E $(G, r)$ eine YES-Instanz von Vertex Cover ist, ist es leicht zu erkennen, dass die gerade konstruierte Instanz Ihres Problems auch eine YES-Instanz ist: einfach die Bezeichnungen , die den Vertices in einer beliebigen Lösung und weisen Sie für jede Kante das entsprechende Element je nachdem, welche der Bezeichnungen oder ausgewählt wurde (wählen Sie willkürlich, wenn beide Bezeichnungen ausgewählt wurden). Diese Lösung verwendet Teilmengen und ist gültig, da nur die entsprechenden für die Entsprechung gelten$S_j$$v_j$$U$$v_bv_c \in E$$(b, c) \in A$$S_b$$S_c$$s$$a_{ij}$Labels, die den (Nicht-) Effekt haben, mehr alsKanten, denen das gleiche Etikett zugewiesen wurde.$|E|$

Es bleibt zu zeigen, dass eine YES-Instanz Ihres Problems impliziert, dass das Original( G , r ) Y X ( i , j ) S m m ∉ { i , j } U $X=(A, a, s)$$(G, r)$ eine YES-Instanz von Vertex Cover ist. Dies ist etwas komplizierter, da eine gültige Lösung bis im Allgemeinen einer Kante eine nicht entsprechende Bezeichnung zuweisen kann , dh , was bedeutet, dass wir dies nicht können notwendigerweise eine gültige Scheitelpunktabdeckung aus einer gültigen Lösung "ablesen" .$Y$$X$$(i, j)$$S_m$$m \notin \{i, j\}$$U$$Y$

Das Zuweisen eines nicht entsprechenden Etiketts ist jedoch mit hohen Kosten verbunden, die die Struktur der Lösung stark einschränken: immer dann, wenn eine Kante vorhanden ist S m m ∉ { i , j } a ( i , j ) , m = 1 Y ( i , j ) ↦ S m Y $(i, j)$ solches Etikett zugewiesen wird , ist die Tatsache dass sicherstellt, dass es die einzige Kante sein muss, der diese Bezeichnung zugewiesen wurde. In jeder Lösung die eine solche nicht entsprechend markierte Kante , könnten wir also eine alternative Lösung wie folgt konstruieren :$S_m$$m \notin \{i, j\}$$a_{(i, j), m} = 1$$Y$$(i, j) \mapsto S_m$$Y'$

1. Wählen Sie willkürlich die neue Bezeichnung für als oder .$S_z$$(i, j)$$S_i$$S_j$
2. Weisen Sie diesem neuen Label . Wenn dies zu einer ungültigen Lösung führt, muss dies daran liegen, dass genau einer anderen Kante , bereits die Bezeichnung zugewiesen wurde . In diesem Fall setzen Sie und fahren Sie mit Schritt 1 fort.$(i, j)$$(i', j')$$z \notin \{i', j'\}$ ( i , j ) = ( i ' , j '$S_z$$(i, j) = (i', j')$

s - 1 $S_z$$s-1$$s$$|E|$$Y''$

Diese Konstruktion ist eindeutig eine Polynomzeit, daher ist Ihr Problem NP-schwer.