Ganzzahlige lineare Programmierung in logarithmischer Anzahl von Variablen

Ich habe gelesen, dass die ganzzahlige lineare Programmierung in Polynom-Zeit lösbar ist, wenn die Anzahl der Variablen fest ist, dh . Wenn die Anzahl der Variablen logarithmisch ansteigt, dh für eine gegebene Eingabe der Größe , ist das Problem in der Polynomzeit noch lösbar oder ist dies ein offenes Problem? $n$ $n \in O(1)$ $n \in O(\log_2(N))$ $N$

cc.complexity-theory np open-problem user3613886
quelle

Können Sie nicht trivial wahre Einschränkungen hinzufügen, um die Größe der Eingabe zu erhöhen?

Joro

Warum solltest du die Größe der Eingabe erhöhen wollen?

user3613886

Die Eingabe so groß zu machen, dass die Anzahl der Variablen logarithmisch ist und Ihrer Frage entspricht.

Joro

aber in der

frage

Ich habe darüber nachgedacht, alle Instanzen als Ihre zu definieren, aber dies könnte den Input exponentiell erhöhen.

Joro

Ich kann diese Frage nur teilweise beantworten.

Ein Ergebnis von Lenstra (später von Kannan und Frank und Tardos verbessert) besagt, dass ILP mit Variablen in der Zeit gelöst werden kann (mal ein Polynom in der Größe des ILP). Daher ist ILP in P, wenn die Anzahl der Variablen . Ich bin nicht sicher, ob ein -Algorithmus bekannt ist oder ob ein solcher Algorithmus der ETH widersprechen würde. $k$ $k^{O(k)}$ $O(\log n/\log\log n)$ $2^{O(k)}$

Diese Information habe ich in der Dissertation von Daniel Lokshtanov gefunden. Hier finden Sie die relevanten Referenzen.

HW Lenstra. Ganzzahlige Programmierung mit einer festen Anzahl von Variablen. Mathematics of Operations Research, 8: 538–548, 1983.
R. Kannan. Minkowskis konvexer Körpersatz und Integer-Programmierung. Mathematics of Operations Research, 12: 415–440, 1987.
Andras Frank und Eva Tardos. Eine Anwendung der simultanen Diophantinen Approximation in der kombinatorischen Optimierung. Combinatorica, 7: 49–65, 1987.

Michael Lampis
quelle

Ich denke, Sie brauchen einen O (k ^ p) -Algorithmus für ein festes p, da sogar ein Algorithmus mit 2 ^ O (k) exponentiell wäre?

user3613886

Entschuldigung, ich habe eine andere Notation als die Frage verwendet. Mit

meine ich die Anzahl der Variablen, und

ist die Größe der Eingabe, so dass ein

Algorithmus eine Polynomzeit wäre, wenn

k

$k$

n

$n$

2^{k}

$2^{k}$

k = O (\log n)

$k=O(\log n)$

Michael Lampis

Aber nehmen wir an, Sie haben nur binäre Variablen, wäre das nicht Brute Force

2^{k}

$2^k$

user3613886

@ user3613886, natürlich, aber das ist ein anderes Problem / eine andere Frage. In der Frage, dass die Variablen binär sind, wurde uns nicht versprochen.

Können Sie nicht trivial wahre Einschränkungen hinzufügen, um die Größe der Eingabe zu erhöhen?

Joro

Ganzzahlige lineare Programmierung in logarithmischer Anzahl von Variablen

Antworten: