Algoritmos exatos de tempo exponencial para programação 0-1

10

Existem algoritmos conhecidos para o seguinte problema que superam o algoritmo ingênuo?

Entrada: Um sistema de desigualdades lineares.Axbm

Saída: Uma solução viável se houver.x{0,1}n

Suponha que e tenham entradas inteiras. Estou interessado nos piores casos.Ab

Austin Buchanan
fonte

Respostas:

14

Se m for superlinear, esse algoritmo refutaria a hipótese do tempo exponencial forte, pois as fórmulas na forma normal conjuntiva são um caso especial da programação 0-1 e o lema da esparsificação nos permite reduzir k -SAT para CNF-SAT em muitas cláusulas linearmente .

No entanto, existe um algoritmo devido a Impagliazzo, Paturi e a mim mesmo que pode resolver esse sistema de desigualdades se o número de fios, ou seja, o número de coeficientes diferentes de zero em for linear. Em particular, se o número de fios for c n , o algoritmo será executado no tempo 2 ( 1 - s ) n , onde s = 1Acn2(1s)n .s=1cO(c2)

Stefan Schneider
fonte
1

Se for pequeno o suficiente, você poderá fazer melhor que o algoritmo ingênuo, ou seja, melhor que 2 n tempo. Aqui "pequeno o suficiente" significa que m é menor que algo como n / lg n . O tempo de execução ainda será exponencial - por exemplo, pode ser 2 n / 2 -, mas será mais rápido que o ingênuo algoritmo.m2nmn/lgn2n/2

Aliás, parece que isso nos permite resolver o problema em mais de tempo para alguns casos em que a matriz A possui um número super-linear de entradas. Não sei como combinar isso com a outra resposta fornecida aqui. Conseqüentemente, você deve verificar minha resposta com cuidado: isso pode indicar que cometi um erro grave em algum lugar.2nA


A abordagem básica: escreva , onde x 0 contém os primeiros n / 2 componentes de x e x 1 contém os últimos n / 2 componentes; e similarmente A = ( A 0 , A 1 ) , onde A 0 tem as n / 2 colunas esquerdas de A e A 1 a n direitax=(x0,x1)x0n/2xx1n/2A=(A0,A1)A0n/2AA1 colunas. Agora A x b pode ser reescrito no formaton/2Axb

A0x0+A1x1b,

ou equivalente,

A0x0bA1x1.

Enumere todas as possibilidades n / 2 para A 0 x 0 e deixe S denotar o conjunto de valores possíveis, ou seja,2n/2A0x0S

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

Da mesma forma, enumere o conjunto de todas as 2 n / 2 possibilidades de b - A 1 x 1 , ou seja,T2n/2bA1x1 1

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

Agora o problema se torna

Conjuntos dados de tamanho 2 n / 2 não existem, s S e t T de tal forma que s t ?S,TZm2n/2sStTst

(Aqui é tomado em sentido horário, ou seja, exigimos que s it i para todos os i .)sitii

O último problema é discutido no CS.StackExchange e, aparentemente, existe um algoritmo para ele que é executado no tempo . Se m for suficientemente pequeno (por exemplo, menor que n / lg n ), então o tempo total de execução será menor que 2 n , conforme desejado.O(2n/2(n/2)m1)mn/lgn2n


Para ajudar a tornar esse resultado mais plausível, aqui está uma intuição muito grosseira. Se considerarmos o caso extremo em que , é claro que isso pode ser resolvido rapidamente. (Na verdade, há um algoritmo muito mais simples para o caso especial em que m = 1 : deixar x i = 1 se A 1 , i0 , caso contrário, x i = 0 ; agora se qualquer solução viável existe, então este x . Irá ser um)m=1m=1xi=1A1,i0xi=0x

DW
fonte
11
O algoritmo da minha resposta também se reduz ao problema vetorial descrito na sua resposta usando o mesmo método, ou seja, divida as variáveis ​​e liste todas as suas atribuições.
Stefan Schneider
2
Existem algoritmos para o problema geral de programação inteira, cujo tempo de execução tem uma dependência de na dimensão e dependência polinomial em todo o resto. Veja dl.acm.org/citation.cfm?id=380857 . 2O(m)
Sasho Nikolov