Minimieren Sie die maximale Komponente einer Summe von Vektoren

Ich möchte etwas über dieses Optimierungsproblem erfahren: Finden Sie für gegebene nicht negative ganze Zahlen eine Funktion die den Ausdruck minimiert$a_{i,j,k}$$f$

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 \in \{0, 1, \ldots, 63\}$ , dh es gibt immer 64 Zeilen (wenn wie im obigen Beispiel geschrieben).
• $j \in \{0, 1\}$ , dh es gibt nur 2 Vektoren pro Zeile.
• $k \in \{0, 1, \ldots, N-1\}$ 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

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

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).$i$$j \in \{0,1\}$$k$$a_{i,j,k}$$i$$j = 0$$j = 1$$k$$3$

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.$r$$f$$k$$64$

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 ₁ ,…, 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 ₁ ,…, c _{3 k} } in k Multisets S ₁ ,…, S _k so aufgeteilt werden, dass die Summe jedes S _j gleich istB ?

Konstruieren Sie bei gegebener Instanz ( B ; c ₁ ,…, 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 _i ∈ S _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 _i ∉ S _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 ₁ ,…, 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 ² 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.