Wie kann die Kardinalität einer Menge und disjunkter Partitionen minimiert werden, die Einschränkungen in der Polynomzeit unterliegen?

Das eigentliche Problem, mit dem ich konfrontiert bin, ist das Folgende.

INSTANZ : Ich habe Mengen und und Matrix für alle und .K : = { 1 , … , k } a i j > 0 i ∈ K j ∈ $N:=\{1,\ldots,n\}$$K:=\{1,\ldots,k\}$$a_{ij}>0$$i\in K$$j\in N$

FRAGE : Ich muss eine Teilmenge von einer möglichst kleinen Größe finden und die Menge indisjunkte Mengen deren Vereinigung gleich so dass ich für alle für alle habe i \ in K_j .$S$$N$$K$$|S|$$K_j$$K$$j\in S$

$$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ $i\in K_j$

Beispiel:

Gegeben ist $n=k=3$ und die Matrix

$$\begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}.$$

In diesem Beispiel sollte $S$ gleich $S=\{1, 2\}$ und $K_1=\{3\}$ und $K_2=\{1,2\}$ .

Ich habe zwei Fakten bemerkt:

• Wenn in N etwas j \ existiert, $j\in N$so dass $a_{ij}\geqslant 1$ für alle $i\in K$ dann ist $S=\{j\}$ und $K_j=K$ ; und
• Wenn es $i\in K$ so dass $a_{ij}<1$ dann ist $S=\emptyset$ .

Meine Frage : Ist es möglich, dieses Optimierungsproblem in Polynomzeit zu lösen (zumindest mit einem Approximationsalgorithmus)?

Das erste, was ich versuchte, war, es in ein bekanntes Problem umzuwandeln und dann einen bekannten Algorithmus dafür anzuwenden. Ich habe darüber nachgedacht, es in ein Set-Cover oder eine Müllverpackung umzuwandeln, aber ich bin gescheitert und finde das auch nicht interessant.

---

Das Problem habe ich versucht zu formulieren.

Ich habe Sätze und und Matrix für alle und . Außerdem habe ich disjunkte Mengen für jedes (ich habe als Eingaben hinzugefügt, weil ich es nicht anders formulieren konnte.)$N:=\{1,\ldots,n\}$$K:=\{1,\ldots,k\}$$a_{ij}>0$$i\in K$$j\in N$$n$$K_j\subset K$$j\in N$$K_j$

Schließlich erhalte ich Folgendes:

$$\begin{align*} & {\underset{S}{\text{minimize}}} & & |S|\\[3pt] & \text{subject to} & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in S,i\in K_j,\\[3pt] & & & S\subseteq N.\\ \end{align*}$$

Vielen Dank.

Auch die Entscheidung Version dieses Problem, bei dem wir versuchen , einfach zu bestimmen , ob es existiert jede machbare Lösung ist NP-schwer durch Reduktion von Exact - Abdeckung . (Die Optimierungsversion, in der wir nach einer praktikablen Lösung suchen, die minimiert , ist eindeutig mindestens so schwierig.)$|S|$

Die einzeilige einspaltige Matrix mit dem Wert 0,5 ist ein Beispiel für eine Eingabe, für die es keine praktikable Lösung gibt. Hier ist ein anderes:

$$\begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}.$$

Erstellen eines Gadgets "höchstens eines auswählen"

Erstens, dass Hinweis , wenn der Maximalwert in irgendeiner Zeile ist , und diese Reihe enthält (mindestens) zwei Kopien von , sagen sich bei und , , dann kann nicht sowohl als auch , da dann einer der beiden folgenden Fälle auftreten muss, die jeweils zu einem Widerspruch führen:$a_i$$x > 0$$x$$a_{ij}$$a_{ij'}$$j' \ne j$$S$$j$$j'$

1. $i \in K_j \cup K_{j'}$ : Angenommen, wlog, dass . Aber dann , was der Anforderung widerspricht, dass .$i \in K_j$$\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$$\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$
2. $i \notin K_j \cup K_{j'}$ : Dann nehme . Aber dann ist , und da in Zeile maximal ist , ist es das höchste, das könnte eindeutig , also müssen wir die gleiche Ungleichung wie zuvor verletzen.$i \in K_p, p \notin \{j, j'\}$$\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$$x$$i$$a_{ip}$$x$

Daher können wir einen Maximalwert auswählen, der sicher höher ist als die Summe aller nicht maximalen Werte in der Zeile, und Kopien dieses Maximalwerts verwenden, um zu erzwingen, dass höchstens eine dieser Spalten in .$S$

Wir können diese Einschränkung "höchstens eine auswählen" in eine Einschränkung "genau eine auswählen" umwandeln, indem wir einen positiven Wert kleiner als 1 als "nicht maximalen" Wert verwenden. Das liegt daran, dass jede Zeile zu einem Teil der gehört , und wenn ist, wird die RHS der Ungleichung für Zeile negativ , sodass es keine Möglichkeit gibt, sie zu erfüllen: also muss mindestens ein in gezwungen werden, so dass .$i$$K_j$$a_{ij} < 1$$i$$j$$S$$a_{ij} \ge 1$

Um sicherzustellen, dass genau eine der Spalten in einer Menge in gezwungen wird , erstellen Sie eine Zeile wie folgt:$T \subseteq N$$S$$a_i$

• Set für jeden .$a_{ij} = n+1$$j \in T$
• Setze für jedes zweite .$a_{ij} = 0.5$$j$

Somit wird die Reduktion von Exact Abdeckung ist einfach: es eine Zeile für jedes Element ist, eine Spalte für jeden Satz, mit , wenn Satz enthält Element und sonst. Beide Richtungen ("Die Eingabe-EC-Instanz ist eine YES-Instanz konstruierte Instanz des OP-Problems eine YES-Instanz ist" und "Die konstruierte Instanz des OP-Problems ist eine YES-Instanz Eingabe-EC-Instanz eine YES-Instanz ist") sind sauber.$a_{ij} = n+1$$j$$i$$a_{ij} = 0.5$$\implies$$\implies$