Genaue Exponentialzeitalgorithmen für 0-1-Programme mit nichtnegativen Daten

9

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

Eingabe: Matrix A und Vektoren b,c , wobei alle Einträge von A,b,c nichtnegative ganze Zahlen sind.

xmax{cTx:Axb,x{0,1}n}

Diese Frage ist eine verfeinerte Version meiner vorherigen Frage. Exakte Exponentialzeitalgorithmen für die 0-1-Programmierung .

Austin Buchanan
quelle

Antworten:

5

Wenn die Anzahl der Koeffizienten ungleich Null in in linear ist , gibt es einen Algorithmus, der dieses Problem in weniger als Zeit löst .An2n

So funktioniert das. Wir verwenden die Standardverbindung zwischen einem Optimierungsproblem und dem entsprechenden Entscheidungsproblem. Um zu testen, ob es eine Lösung in der und , bilden wir ein Entscheidungsproblem: Wir werden die Einschränkung an die Matrix anhängen und testen ob es ein so dass und . Insbesondere werden wir eine neue Matrix indem wir und eine zusätzliche Zeile hinzufügen, die , und wir werden bilden indem wirxAxbcTxαcTxαAxAxbcTxαAAcTbbund neben einer zusätzlichen Zeile mit . Wir erhalten ein Entscheidungsproblem: Gibt es so dass ? Die Antwort auf dieses Entscheidungsproblem sagt uns, ob es eine Lösung für das ursprüngliche Optimierungsproblem von Wert oder höher gibt. Darüber hinaus kann, wie in der Antwort auf Ihre vorherige Frage erläutert , dieses Entscheidungsproblem in weniger als Zeit gelöst werden, wenn die Anzahl der Nicht-Null-Koeffizienten in in linear ist (und somit die Anzahl der Nicht-Null-Koeffizienten) Nullkoeffizienten in sind linear in ). Jetzt können wir die binäre Suche fürαx{0,1}nAxbα2nAnAnαum Ihr Optimierungsproblem in weniger als Zeit zu lösen .2n

Ich danke AustinBuchanan und Stefan Schneider für ihre Hilfe beim Debuggen einer früheren Version dieser Antwort.

DW
quelle
Können Sie eine stärkere Antwort geben: "Es gibt einen Zeit- -Algorithmus" oder "Ein Algorithmus, der schneller ist als ..."? O(2n/2)O(2n)
Austin Buchanan
@AustinBuchanan, wenn die Anzahl der Dimensionen von klein genug ist, gibt es einen -Algorithmus, wie in meiner Antwort auf die andere Frage dokumentiert . Das ist das Beste, was ich tun kann. Ich weiß nicht, wie ich es besser machen soll. Vielleicht können andere eine stärkere Antwort geben! bO(2n/2)
DW
O(2n/2) Zeit gilt immer dann, wenn die Anzahl der Einschränkungen ? O(1)
Austin Buchanan
4

Wenn wir das Minimierungsproblem , dann zeigt die folgende Reduktion, dass ein Algorithmus in der Zeit läuft für würde das SETH widerlegen. Eine Neuformulierung beweist das gleiche Ergebnis für das beabsichtigte Problem (die Maximierungsversion).miny{cTy:Ayb,y{0,1}n}O(2δn/2)δ<1

eine Instanz von CNF-SAT mit Variablen eine 0-1-IP mit zwei Variablen für jede Variable in der SAT-Instanz. Wie üblich wird die Klausel als . dann für jede Variable in der SAT-Instanz eine Einschränkung . Das Ziel ist es, zu minimieren . Das Ziel des IP ist wenn die SAT-Instanz erfüllt werden kann.Φ=i=1mCi{xj}j=1nyj,y¯jxj(x1x¯2x3)y1+y¯2+y31xjyj+y¯j1j=1n(yj+y¯j)n

Danke an Stefan Schneider für die Korrektur.

Update: Bei Problemen, die so schwer wie CNF-Sat sind, vermuten die Autoren, dass SET COVER nicht in der Zeit , gelöst werden kann , wobei sich auf die Anzahl der Sätze bezieht. Wenn dies zutrifft, würde dies zeigen, dass mein Problem nicht auch in der Zeit gelöst werden kann .O(2δn)δ<1nO(2δn)

Update 2. Soweit ich sagen kann, kann mein Problem unter der Annahme von SETH nicht in der Zeit gelöst werden , da gezeigt wurde, dass Hitting Set (mit einem Grundsatz der Größe ) nicht möglich ist gelöst in der Zeit .O(2δn)nO(2δn)

Austin Buchanan
quelle
3
Da Sie die Anzahl der Variablen verdoppeln, zeigt dies meiner Meinung nach nur, dass ein Algorithmus für dieses Problem mit Laufzeit SETH widersprechen würde. O(2δn/2)
Stefan Schneider
Warten Sie ... die Autoren von On Problems so Hard wie CNF-SAT geben an, dass "für jedes ein Algorithmus zum Schlagen von Set SETH verletzen würde". Funktioniert das nicht ϵ<1O(2ϵn)
Austin Buchanan