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 linearen Ungleichungen. $Ax \le b$ $m$

Output: eine realisierbare Lösung , falls vorhanden. $x^*\in \{0,1 \}^n$

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

np-hardness integer-programming exp-time-algorithms Austin Buchanan
quelle

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, -SAT in linear vielen Klauseln auf CNF-SAT zu reduzieren . $m$ $k$

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 , läuft der Algorithmus in der Zeit , wobei $A$ $cn$ $2^{(1-s)n}$ . $s=\frac1{c^{O(c^2)}}$

Stefan Schneider
quelle

1

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

Übrigens sieht es so aus, als könnten wir das Problem in einigen Fällen, in denen die Matrix 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. $2^n$ $A$

Der grundlegende Ansatz: schreibe , wobei die ersten Komponenten von und die letzten Komponenten enthält; und ähnlich , wobei die linken Spalten von und die rechten $x=(x_0,x_1)$ $x_0$ $n/2$ $x$ $x_1$ $n/2$ $A=(A_0,A_1)$ $A_0$ $n/2$ $A$ $A_1$ Spalten. Jetzt kann in der Form neu geschrieben werden $n/2$ $Ax \le b$

A_{0} x_{0} + A_{1} x_{1} \leq b,

$A_0 x_0 + A_1 x_1 \le b,$

oder gleichwertig,

A_{0} x_{0} \leq b - A_{1} x_{1} .

$A_0 x_0 \le b - A_1 x_1.$

Zählen Sie alle Möglichkeiten für und lassen Sie die Menge möglicher Werte bezeichnen, dh $2^{n/2}$ $A_0 x_0$ $S$

S = {A_{0} x_{0} : x_{0} \in {0, 1}^{n / 2}} .

$S=\{A_0 x_0 : x_0 \in \{0,1\}^{n/2}\}.$

$T$ $2^{n/2}$ $b - A_1 x_1$

T = {b - A_{1} x_{1} : x_{1} \in {0, 1}^{n / 2}} .

$T = \{b - A_1 x_1 : x_1 \in \{0,1\}^{n/2}\}.$

Jetzt wird das Problem

$S,T \subseteq \mathbb{Z}^{m}$ $2^{n/2}$ $s\in S$ $t \in T$ $s\le t$

$\le$ $s_i \le t_i$ $i$

$O(2^{n/2} (n/2)^{m-1})$ $m$ $n/\lg n$ $2^n$

$m=1$ $m=1$ $x_i=1$ $A_{1,i}\le 0$ $x_i=0$ $x$

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

2^{O (m)}

$2^{O(m)}$

Genaue Exponentialzeitalgorithmen für die 0-1-Programmierung

Antworten: