Minimale kumulative Sollsumme

Betrachten Sie dieses Problem: Suchen Sie anhand einer Liste endlicher Mengen eine Reihenfolge , die | minimiert s 1 | + | s 1 ∪ s 2 | + | s 1 ∪ s 2 ∪ s 3 | + … .$s_1, s_2, s_3, \ldots$$|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$

Gibt es dafür bekannte Algorithmen? Was ist ihre Komplexität? Ich konnte mir noch keinen effizienten optimalen Algorithmus ausdenken, aber es ist auch nicht offensichtlich in NP-Hard.

Dieses Problem hängt tatsächlich mit einem Planungsproblem zusammen, das als "Prioritätsbeschränkte Planung zur Minimierung der gewichteten Abschlusszeit" bekannt ist. Das Problem ist wie folgt: Bei einer Reihe von Jobs, bei denen jeder Job eine Verarbeitungszeit (p) und ein Gewicht (w) aufweist und für die Jobs ein Prioritätsdiagramm definiert ist. Ziel ist es, die Jobs auf einem einzelnen Computer (nicht präemptiv) so zu planen, dass die Prioritätsbeschränkungen statistisch festgelegt werden und die Summe der gewichteten Abschlusszeiten minimiert wird. Das Problem ist NP-hart und eine 2-Approximation ist bekannt.

Reduktion vom minimalen kumulativen Summenproblem auf das Problem der prioritätsbeschränkten Zeitplanung: Erstellen Sie für jedes Element einen Job mit p = 1, w = 0. Erstellen Sie auch für jede Menge einen Job mit p = 0, w = 1. Erstellen Sie das Prioritätsdiagramm, so dass Wenn das Element , muss e vor S eingeplant werden . Ich denke, dieser Sonderfall des Scheduling-Problems ist auch NP-schwer.$e \in S$$e$$S$

Siehe die folgenden Links,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps

Shalmoli Gupta hat bereits erklärt, dass das allgemeine Problem NP-schwer ist. Deshalb habe ich mich entschlossen, zu untersuchen, ob irgendwelche Sonderfälle polynomiell lösbar sind. Schließlich fand ich eine Lösung für den Sonderfall von Mengen, die einen Baum repräsentieren, oder allgemeiner eine serielle parallele Reihenfolge durch Einbeziehung von Teilmengen, wobei alle unvergleichbaren Mengen disjunkt sind.

Eine Eigenschaft, die die Sache einfacher macht, ist, wenn die Liste der Mengen unter der Überschneidung geschlossen wird. Wenn ist, gibt es eine optimale Reihenfolge, in der s 1 vor s 2 steht . Wir können WLOG annehmen, dass die optimale Reihenfolge eine lineare Erweiterung der durch die Einbeziehung von Teilmengen gegebenen Teilreihenfolge ist.$s_1 \subseteq s_2$$s_1$$s_2$

Da alle Teilmengen einer Menge in der Reihenfolge davor erscheinen, bedeutet dies, dass der Betrag, der von einer gegebenen Menge zur laufenden Summe addiert wird, unabhängig davon, wo er erscheint, festgelegt ist. Wenn die Liste der Mengen ist, sind die zusätzlichen Kosten einer Menge die Anzahl der Elemente in s, die sich nicht in einer Teilmenge von s befinden, die in S erscheint . Wenn derselbe Satz in S mehrfach vorkommt , können wir beliebig einen auswählen, um zuerst zu beginnen und die anderen 0 kosten zu lassen.$S$$S$$S$

Dies bedeutet, dass das Problem dem Problem der minimalen gewichteten Abschlusszeit bei der Einzelmaschinenplanung mit Prioritätsbeschränkungen entspricht. In diesem Problem eine Reihe von Jobs mit Gewichten gegeben, und Zeiten t j , und eine partielle Ordnung auf dem Arbeits P , wollen wir eine Ordnung der Arbeit finden, der die gewichteten Gesamtausführungszeit minimiert, dh$w_j$$t_j$$P$

$\sum_{i=1}^{n} w_{j_i} \left(\sum_{k=1}^{i} t_{j_k}\right)$

vorbehaltlich der Präzedenzbedingungen . Das minimale kumulative Mengenproblem bei geschlossenen Mengen mit Überschneidungen kann dadurch behoben werden, dass für jede Menge ein Auftrag erstellt wird, bei dem jeder Auftrag das Gewicht 1 hat, die Zeit den oben definierten inkrementellen Kosten entspricht und P die Reihenfolge ist, die durch die Einbeziehung von Teilmengen angegeben wird.$P$$P$

Wie sich herausstellt, ist dieses Problem auch für allgemeines NP-schwer . Bestimmte Sonderformen von P können jedoch in der Polynomzeit gelöst werden.$P$$P$

In dieser Arbeit wird ein -Algorithmus für den Fall serieller paralleler Ordnungen P angegeben (der auch den wichtigen Fall von Bäumen einschließt). Leider konnte ich nicht auf dieses Papier zugreifen, und ich beschloss, es selbstständig neu zu erfinden. Folgendes habe ich mir ausgedacht.$O(nlogn)$$P$

Um dieses Problem zu lösen, sind mehrere Beobachtungen erforderlich.

Erstens besteht die optimale Lösung in Abwesenheit von Prioritätsbeschränkungen darin, die Jobs einfach in der Reihenfolge zu sortieren, in der t j erhöht wird . Der Einfachheit halber beziehe ich mich hier auf den Wert des Jobs, abgekürzt mitv(j). Beachten Sie, dasses unmöglich ist, diese Komplexität zuübertreffen, da die SortierungO(nlogn)ist.$\frac{t_j}{w_j}$$v(j)$$O(nlogn)$

Regel 1 Sei und b Jobs, so dass a < b ∈ P und b a abdecken. Wenn v ( a ) < v ( b ) ist , können wir die Bedingung a < b fallen lassen, ohne die optimale Reihenfolge oder den objektiven Wert zu beeinflussen.$a$$b$$a < b \in P$$v(a) < v(b)$$a < b$

$b$$a$

$v(a) = v(b)$

$v(a) \leq v(b)$$a < b$

$w_c = w_a + w_b$$t_c = t_a + t_b$$P$

$w_at_b$$c$$ab$

$a$$b$$v(a) > v(b)$$a$$b$

$a, x_1, x_2, \ldots, b$$P$$x_i$$a$$b$$x_i$$x'$$v(x')$$v(x') \leq v(a)$$x'$$a$$v(x') \geq v(b)$$x'$$b$$v(a) < v(x') < v(b)$$v(a) > v(b)$

$O(n^2)$$P$$P$

$P$$P_1$$P_2$$C_1$$C_2$$P$$C_2$$C_1$

$P$$S_1$$S_2$

$O(n^2)$$O(nlogn)$

Insbesondere wenn ein Unterproblem nur Knoten enthält, bei denen die Prioritätsbeschränkungen der Reihenfolge der Werte entsprechen, können wir die Prioritätsbeschränkungen vollständig vergessen und nur die Werte betrachten. Dies wird durch dieselbe Invariante sichergestellt, die dafür gesorgt hat, dass die Lösungen im vorherigen Algorithmus nach Ketten sortiert sind.

Anstatt für jedes Teilproblem eine sortierte Kette zu berechnen, stellen wir die optimale Lösung für ein Teilproblem als ein Paar von Fibonacci-Heaps dar, einer ein Min-Heap und einer ein Max-Heap, die beide alle Jobs des Teilproblems enthalten. Dies bedeutet, dass wir das minimale oder maximale Element der Lösung in logarithmischer Zeit abrufen können.

$P$$P$

Für eine parallele Komposition führen wir einfach die Heap-Paare zusammen. Der neue Min-Heap ist die Zusammenführung des Min-Heaps aus jedem Unterproblem und ebenfalls mit dem Max-Heap. Beachten Sie, dass Fibonacci-Haufen in konstanter Zeit zusammengeführt werden können.

Sobald wir ein Heap-Paar haben, das die Lösung für das gesamte Problem darstellt, können wir die tatsächliche Lösungsreihenfolge finden, indem wir den Min-Heap herausnehmen, bis er leer ist. Danach machen wir alle Ersetzungen von Regel 2 rückgängig, um eine Lösung für das ursprüngliche Problem zu erhalten.

$O(nlogn)$