Genaue Exponentialzeitalgorithmen für die 0-1-Programmierung

10

Gibt es bekannte Algorithmen für das folgende Problem, die den naiven Algorithmus übertreffen?

Eingabe: Ein System von m linearen Ungleichungen.Axbm

Output: eine realisierbare Lösung , falls vorhanden.x{0,1}n

Angenommen, und b haben ganzzahlige Einträge. Ich interessiere mich für Worst-Case-Grenzen.Ab

Austin Buchanan
quelle

Antworten:

14

Wenn superlinear ist, würde ein solcher Algorithmus die Hypothese der starken Exponentialzeit widerlegen, da Formeln in konjunktiver Normalform ein Sonderfall der 0-1-Programmierung sind und das Sparsification Lemma es uns ermöglicht, k -SAT in linear vielen Klauseln auf CNF-SAT zu reduzieren .mk

Es gibt jedoch einen Algorithmus von Impagliazzo, Paturi und mir , der ein solches Ungleichungssystem lösen kann, wenn die Anzahl der Drähte, dh die Anzahl der Koeffizienten ungleich Null in linear ist. Insbesondere wenn die Anzahl der Drähte c n ist , läuft der Algorithmus in der Zeit 2 ( 1 - s ) n , wobei s = 1 istAcn2(1s)n .s=1cO(c2)

Stefan Schneider
quelle
1

Wenn klein genug ist, können Sie es besser machen als der naive Algorithmus, dh besser als 2 n Mal. Hier bedeutet "klein genug", dass m kleiner ist als etwas wie n / lg n . Die Laufzeit ist immer noch exponentiell - z. B. 2 n / 2 -, aber schneller als der naive Algorithmus.m2nmn/lgn2n/2

Übrigens sieht es so aus, als könnten wir das Problem in einigen Fällen, in denen die Matrix A eine superlineare Anzahl von Einträgen aufweist, schneller als lösen . Ich weiß nicht, wie ich das mit der anderen Antwort hier in Einklang bringen soll. Daher sollten Sie meine Antwort sorgfältig prüfen: Dies könnte darauf hinweisen, dass ich irgendwo einen schwerwiegenden Fehler gemacht habe.2nA


Der grundlegende Ansatz: schreibe , wobei x 0 die ersten n / 2 Komponenten von x und x 1 die letzten n / 2 Komponenten enthält; und ähnlich A = ( A 0 , A 1 ) , wobei A 0 die linken n / 2 Spalten von A und A 1 die rechten n hatx=(x0,x1)x0n/2xx1n/2A=(A0,A1)A0n/2AA1 Spalten. Jetzt kann A x b in der Form neu geschrieben werdenn/2Axb

A0x0+A1x1b,

oder gleichwertig,

A0x0bA1x1.

Zählen Sie alle Möglichkeiten für A 0 x 0 auf und lassen Sie S die Menge möglicher Werte bezeichnen, dh2n/2A0x0S

S={A0x0:x0{0,1}n/2}.

T2n/2bA1x1

T={bA1x1:x1{0,1}n/2}.

Jetzt wird das Problem

S,TZm2n/2sStTst

sitii

O(2n/2(n/2)m1)mn/lgn2n


m=1m=1xi=1A1,i0xi=0x

DW
quelle
1
Der Algorithmus aus meiner Antwort reduziert sich mit der gleichen Methode auch auf das in Ihrer Antwort beschriebene Vektorproblem, dh teilt die Variablen auf und listet alle ihre Zuordnungen auf.
Stefan Schneider
2
2O(m)