Selecione um subconjunto das colunas na matriz , é fácil?

2

Quero saber se esse problema é solucionável em tempo polinomial ou não?

O problema é: Dada uma matriz com valor inteiro não negativo de tamanho dois números inteiros não negativos e .2×nb<nc

A questão é: Encontre um subconjunto das colunas de cardinalidade no máximo modo que a soma de cada linha sobre o subconjunto das colunas seja maior que . Retorne no se esse subconjunto não existir.bc

Não posso mostrar que é NP-difícil.

EDITAR:

Minha tentativa de provar dureza : de acordo com as sugestões do Filmus, tentei reduzir PARTITION (uma instância é dada pelo conjunto de números inteiros não negativos ) para o meu problema. Eu falhei, é claro. O pensamento que eu não entendi é como o particionamento de um conjunto de números inteiros não negativos está relacionado a esse problema? Quero dizer, no meu problema, quero escolher um subconjunto de para maximizar algo. Não consigo ver como isso é uma partição. Eu tentei muitos pensamentos, mas não posso escrevê-los todos aqui:{a1,,an}{1,,n}

  • Eu tentei criar a matriz com apenas na primeira linha e na segunda linha.a2ia2i+1
  • Eu cansei de fazer a primeira linha classificada em ordem crescente e a segunda linha em ordem decrescente.
  • Tentei dividir o em dois valores e modo que e crie a matriz com na primeira linha e na segunda linha.aiαiβiai=αi+βiαiβi

Alguém pode me explicar, intuitivamente, como posso usar PARTITION para mostrar a dureza NP do meu problema? Você não precisa dar a solução.

Minha solução para resolver o problema :

Eu tentei esta solução. Suponha, sem perder a generalidade, que a primeira linha da matriz seja classificada em ordem crescente. (A segunda linha da matriz não precisa ser classificada, caso contrário, o problema é trivial.)

Agora, pegue as últimas colunas da matriz.b

  • Se a soma da primeira linha for menor que do que a efetuada. Nenhuma solução existe.c
  • Senão, a soma da primeira linha nas últimas colunas é maior que e veja a soma da segunda linha. bc
    • Se a soma da segunda linha nas últimas colunas for maior que que nós, fizemos. Retorne as últimas colunas.bcb
    • Senão, a soma da primeira linha sobre as colunas é maior que mas a soma da segunda linha sobre as colunas é menor que . Bem, aqui temos um problema.bcbc
Brika
fonte
Neste ponto, é difícil dar uma dica sem abrir mão da solução.
Yuval Filmus
Eu adicionei a solução à minha resposta. Da próxima vez, tente mais antes de desistir.
Yuval Filmus

Respostas:

6

Dica: mostre que é NP-difícil por redução de EQUAL-PARTITION, a variante de PARTITION na qual exigimos que ambas as partes tenham tamanhos iguais (consulte uma pergunta em math.se ).

Dada uma instância {x1,,xn} EQUAL-PARTITION (com xi>0), considere uma instância do seu problema com b=n/2, c=i(M+xi)/21 para grande o suficiente M (Eu penso isso M=maxixi deve bastar) e a matriz

[M+x1M+xnM+ixin/2x1M+ixin/2xn].
Yuval Filmus
fonte
Obrigado. Tentei fazer isso usando PARTITION, como você sugeriu. Dada uma instância de PARTITION,A={a1,,an}. Crio uma instância do meu problema da seguinte maneira:b=n/2 (Eu suponho que n é par), c=i=1nai/2 e a matriz é dada por [a1ana1an]. PARTITION é resolvido se o problema for resolvido em que o subconjunto de colunas é aquele com índices na primeira partição ou na segunda partição. Eu acho que isso não está exatamente correto, certo?
Brika 04/02
Sua instância é fácil de resolver - use o n/2 maior não negativo ais e veja se eles somam pelo menos iai/2. Então não, não funciona. Tente escrever uma prova formal na próxima vez. Além disso, verifique a definição exata de PARTITION (por exemplo, na Wikipedia).
Yuval Filmus
6
@Yuval. A matriz tem entradas não negativas, não é?
Zighalo
5
Ah - eu perdi essa condição. Mas talvez a redução possa ser ajustada de alguma forma.
Yuval Filmus
3
@Brika Não necessariamente. A ideia funciona se modificada adequadamente.
Yuval Filmus