Minimieren Sie die maximale Komponente einer Summe von Vektoren

11

Ich möchte etwas über dieses Optimierungsproblem erfahren: Finden Sie für gegebene nicht negative ganze Zahlen eine Funktion die den Ausdruck minimiert fai,j,kf

maxkiai,f(i),k

Ein Beispiel mit einer anderen Formulierung könnte es klarer machen: Sie erhalten eine Reihe von Vektorsätzen wie

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Wählen Sie einen Vektor aus jedem Satz, so dass die maximale Komponente ihrer Summe minimal ist. Zum Beispiel können Sie wählen

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

mit der maximalen Komponente gleich 2, was hier eindeutig optimal ist.

Ich bin gespannt, ob dies ein bekanntes Problem ist und welche problemspezifischen Näherungslösungsmethoden zur Verfügung stehen. Es sollte schnell und einfach zu programmieren sein (kein ILP- Solver usw.). Es ist keine genaue Lösung erforderlich, da dies nur eine Annäherung an das eigentliche Problem darstellt.


Ich sehe, dass ich einige Details zu den Probleminstanzen hätte hinzufügen sollen, an denen ich interessiert bin:

  • i{0,1,,63} , dh es gibt immer 64 Zeilen (wenn wie im obigen Beispiel geschrieben).
  • j{0,1} , dh es gibt nur 2 Vektoren pro Zeile.
  • N.k{0,1,,N1} wobei (die Vektorlänge) zwischen 10 und 1000 liegt.N

Darüber hinaus ist in jeder Zeile die Summe der Elemente aller Vektoren gleich, dh

i,j,j:kai,j,k=kai,j,k

und die Summe der Elemente des Summenvektors ist kleiner als seine Länge, dh

kiai,f(i),k<N
Maaartinus
quelle
4
Es ist nicht schwer, das 3-Partitions-Problem auf Ihr Problem zu reduzieren . Dies bedeutet, dass Ihr Problem NP-vollständig ist, selbst wenn die Zahlen unär angegeben sind, und dies schließt einen der gängigen Ansätze für einen Approximationsalgorithmus aus.
Tsuyoshi Ito
Danke für die Korrekturen und danke an @Tsuyoshi Ito für den Einblick. Wenn ich es richtig verstehe, macht die Beschränkung auf zwei Vektoren pro Zeile (die ich vergessen habe anzugeben) die Reduzierung ungültig und kann das Problem erheblich erleichtern.
Maaartinus
Sie haben Recht, die Reduzierung des 3-Partitions-Problems, an das ich gedacht habe, funktioniert nicht, wenn nur zwei Vektoren pro Zeile vorhanden sind.
Tsuyoshi Ito
Es gibt also Kombinationen zu vergleichen? ji
Jason Kleban
@ uosɐſ: Um genau zu sein, gibt es mögliche Kombinationen, wobei J = 2 die Anzahl der Möglichkeiten für j und I = 64 die Anzahl der Möglichkeiten für i ist . JI=264J=2jI=64i
Maaartinus

Antworten:

7

Reduktion von 3SAT auf die Zwei-Vektor-Version: Wenn eine Formel gegeben ist, lassen Sie Variablen, j { 0 , 1 } und k Indexklauseln indizieren. Sei a i , j , k die Häufigkeit , mit der die Variable i in Klausel k positiv (wenn j = 0 ) oder negativ (wenn j = 1 ) erscheint . OPT ist kleiner als 3, wenn die Formel erfüllt werden kann (die Bijektion ist offensichtlich).ij{0,1}kai,j,kij=0j=1k3

Wie ich dieses Problem angreifen würde: große Nachbarschaftssuche. Beginnen Sie mit einer beliebigen Lösung. Wähle zufällig Zeilen. Verwenden Sie Brute Force, um die beste Lösung zu finden, bei der sich f nur in diesen Zeilen ändern kann - sehr machbar für selbst mäßiges k , da die Problemgröße 64 Zeilen beträgt . Wiederholen.rfk64

Hallo Mods
quelle
1
Dies ist eine schöne Reduzierung. Ich bin mir nicht sicher, warum es keine Up-Votes gibt. Wie auch immer, hier ist meine +1.
Tsuyoshi Ito
1
Ich denke, Sie sollten etwas mehr auf die Reduzierung eingehen. Insbesondere haben Sie gut versteckt, vielleicht zu gut, wie es die Bijektion ein bisschen schwer zu sehen macht. f
Raphael
7

Wir können die Komplexität eines Problems nicht diskutieren, wenn die Problemgröße auf eine Konstante festgelegt ist, da sich die Komplexitätstheorie (größtenteils) mit dem asymptotischen Verhalten der Komplexität des Problems befasst, da die Problemgröße gegen unendlich tendiert. Hier betrachte ich sowohl die Anzahl der Zeilen als auch die Abmessung der Vektoren als Variablen.

Dann ist das Problem NP-vollständig, selbst wenn die Zahlen in der Eingabe unär sind. Dies ist keine Antwort auf Ihre Frage, weil Sie nach Annäherung fragen, aber es ist etwas.

Definieren Sie das Problem genau:

Instanz : n Vektorpaare a i , b i ∈ ∈ m ( i ∈ {1,…, n }) und K ∈ ∈, alle in unär.
Frage : Können wir für jedes i entweder a i oder b i wählen, so dass die Summe dieser n Vektoren höchstens K in jeder Koordinate hat?

Das Folgende ist ein bekanntes NP-vollständiges Problem, das als 3-Partition bezeichnet wird :

3-Partitions-
Instanz : B ∈ ∈ und 3 k ganze Zahlen c 1 ,…, c 3 k zwischen B / 4 und B / 2, exklusiv, so dass ∑ i = 1 3 k c i = kB , alle in unär.
Frage : Kann das Multiset { c 1 ,…, c 3 k } in k Multisets S 1 ,…, S k so aufgeteilt werden, dass die Summe jedes S j gleich istB ?

Konstruieren Sie bei gegebener Instanz ( B ; c 1 ,…, c 3 k ) des 3-Partitions-Problems eine Instanz des obigen Problems wie folgt. Für jedes i = 1,…, 3 k und j = 1,…, k konstruieren wir ein Paar von 4 k- dimensionalen Vektoren, die die Wahl darstellen, ob c i zu S j gehört oder nicht:

  • Der Vektor, der die Wahl " c iS j " darstellt, hat nur einen Eintrag ungleich Null, nämlich ( k - 1) c i an der j- ten Koordinate.
  • Der Vektor, der die Wahl " c iS j " darstellt, hat auch nur einen Eintrag ungleich Null, nämlich B an der ( k + i ) -ten Koordinate.

Es ist nicht schwer zu erkennen, dass die Instanz ( B ; c 1 ,…, c 3 k ) des 3-Partitions-Problems genau dann eine Lösung hat, wenn es eine Möglichkeit gibt, aus jedem der konstruierten 3 k 2 einen Vektor auszuwählen Paare, so dass alle Koordinaten der Summe dieser Vektoren höchstens ( k −1) B sind . (In diesem Fall sind tatsächlich alle Koordinaten der Summe gleich ( k −1) B. ) Dies ist also eine Reduzierung vom 3-Partitions-Problem auf das obige Problem.

Bisher habe ich die beiden zusätzlichen Einschränkungen am Ende der Frage ignoriert, aber beide lassen sich leicht durchsetzen, indem diese Reduzierung geringfügig geändert wird. Die Bedingung, dass die Summe der Elemente jedes Vektors gleich ist, kann durch Anhängen von Dummy-Koordinaten erzwungen werden, die nur 0 oder 1 enthalten. Die Bedingung, dass diese Summe kleiner als die Dimension ist, kann durch Anhängen von Dummy-Koordinaten erzwungen werden, die nur 0 enthalten.

Tsuyoshi Ito
quelle
N