Algorithmes à temps exponentiel exact pour la programmation 0-1

10

Existe-t-il des algorithmes connus pour le problème suivant qui ont battu l'algorithme naïf?

Entrée: Un système de m inégalités linéaires.Axbm

Résultat: une solution réalisable s'il en existe une.x{0,1}n

Supposons que et b ont des entrées entières. Je m'intéresse au pire des cas.Ab

Austin Buchanan
la source

Réponses:

14

Si est superlinéaire, un tel algorithme réfuterait l'hypothèse de temps exponentiel fort, car les formules sous forme normale conjonctive sont un cas particulier de programmation 0-1 et le lemme de sparsification nous permet de réduire k -SAT en CNF-SAT sur de nombreuses clauses linéairement .mk

Cependant, il existe un algorithme dû à Impagliazzo, Paturi et moi - même qui peut résoudre un tel système d'inégalités si le nombre de fils, c'est-à-dire le nombre de coefficients non nuls dans est linéaire. En particulier, si le nombre de fils est c n , l'algorithme s'exécute dans le temps 2 ( 1 - s ) n , où s = 1Acn2(1s)n .s=1cO(c2)

Stefan Schneider
la source
1

Si est suffisamment petit, vous pouvez faire mieux que l'algorithme naïf, c'est-à-dire mieux que 2 n fois. Ici, «assez petit» signifie que m est plus petit que quelque chose comme n / lg n . Le temps d'exécution sera toujours exponentiel - par exemple, il pourrait être 2 n / 2 fois - mais il sera plus rapide que l'algorithme naïf.m2nmn/lgn2n/2

Soit dit en passant, il semble que cela nous permette de résoudre le problème en un temps inférieur à dans certains cas où la matrice A a un nombre d'entrées super-linéaire. Je ne sais pas comment concilier cela avec l'autre réponse fournie ici. Par conséquent, vous devriez vérifier attentivement ma réponse: cela pourrait indiquer que j'ai commis une grave erreur quelque part.2nA


L'approche de base: écrire , où x 0 contient les n / 2 premiers composants de x et x 1 contient les n / 2 derniers composants; et de même A = ( A 0 , A 1 ) , où A 0 a les n / 2 colonnes gauche de A et A 1 le n droitx=(x0,x1)x0n/2xx1n/2A=(A0,A1)A0n/2AA1 colonnes. Maintenant, A x b peut être réécrit sous la formen/2Axb

A0x0+A1x1b,

ou équivalent,

A0x0bA1x1.

Énumérer toutes les possibilités pour A 0 x 0 et laisser S désigner l'ensemble des valeurs possibles, c'est-à-dire2n/2A0x0S

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

T2n/2bA1x1

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

Maintenant, le problème devient

S,TZm2n/2sStTst

sitii

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


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

DW
la source
1
L'algorithme de ma réponse se réduit également au problème de vecteur décrit dans votre réponse en utilisant la même méthode, c'est-à-dire diviser les variables et lister toutes leurs affectations.
Stefan Schneider
2
2O(m)