Outra variante de PARTITION

13

Eu tenho uma redução do seguinte problema de partição para um determinado problema de agendamento:

Entrada: Uma lista de números inteiros positivos em ordem não decrescente.uma1uman

Pergunta: Existe um vetor tal que(x1,...,xn){-1,1}n

k i = 1 a i x i0

Eu=1numaEuxEu=0 0e
Eu=1kumaEuxEu0 0para todos k{1,...,n}

Sem a segunda condição, é apenas PARTITION, portanto, NP-hard. Mas a segunda condição parece fornecer muitas informações adicionais. Gostaria de saber se existe uma maneira eficiente de decidir essa variante. Ou ainda é difícil?

Thomas Kalinowski
fonte

Respostas:

15

Aqui está uma redução de PARTITION para esse problema. Seja uma instância de PARTITION. Suponha que .a 1a 2a n(uma1,...,uman)uma1uma2uman

Seja um "número muito grande", por exemplo, . Considere a instância do nosso problema.N = ( Σ n i = 1 | um de i | ) + 1 N , ... , N 5 n  vezes , N + um 1 , ... , N + um n , 4 N , ... , 4 N n  vezesNN=(Eu=1n|umaEu|)+1

N,...,N5n vezes,N+uma1,...,N+uman,4N,...,4Nn vezes
  1. Se houver uma solução para PARTITION, é uma solução para o nosso problema.1 , , 1 4 n  vezes , - x 1 , , - x n , x 1 , , x n , - 1 , , - 1 times n  vezesx1,...,xn

    1,...,14n vezes,-x1,...,-xn,x1,...,xn,-1,...,-1n vezes
  2. (x1,...,x5n,y1,...,yn,z1,...,zn)Eu=1numaEuyEu0 0(modN)

    Eu=1numaEuyEu=0
    (y1,...,yn)
Yury
fonte
Obrigado Yury. Na minha aplicação, é essencial que a lista de entrada seja ordenada de maneira não decrescente, e a entrada na sua redução não é. Modificarei a pergunta para tornar o requisito do pedido mais explícito. (N,uma1,...,uman,N)
Thomas Kalinowski
@ Thomas: Eu não percebi isso. Agora eu atualizei minha solução.
Yury