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

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\times n$ $b<n$ $c$

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. $b$ $c$

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: $\{a_1,\ldots,a_n\}$ $\{1,\ldots,n\}$

Eu tentei criar a matriz com apenas na primeira linha e na segunda linha. $a_{2i}$ $a_{2i+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. $a_i$ $\alpha_i$ $\beta_i$ $a_i=\alpha_i+\beta_i$ $\alpha_i$ $\beta_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.
- Se a soma da segunda linha nas últimas colunas for maior que que nós, fizemos. Retorne as últimas colunas. $b$ $c$ $b$
- 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. $b$ $c$ $b$ $c$

algorithms complexity-classes 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:

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 $\{x_1,\ldots,x_n\}$ EQUAL-PARTITION (com $x_i > 0$ ), considere uma instância do seu problema com $b = n/2$ , $c = \sum_i (M+x_i)/2 - 1$ para grande o suficiente $M$ (Eu penso isso $M = \max_i x_i$ deve bastar) e a matriz

[\begin{matrix} M + x_{1} & \dots & M + x_{n} \\ M + \frac{\sum_{i} x_{i}}{n / 2} - x_{1} & \dots & M + \frac{\sum_{i} x_{i}}{n / 2} - x_{n} \end{matrix}] .

$\begin{bmatrix} M+x_1 & \cdots & M+x_n \\ M+\frac{\sum_i x_i}{n/2}-x_1 & \cdots & M+\frac{\sum_i x_i}{n/2}-x_n \end{bmatrix}.$

Yuval Filmus
fonte

Obrigado. Tentei fazer isso usando PARTITION, como você sugeriu. Dada uma instância de PARTITION,

A = {a_{1}, \dots, a_{n}}

$A=\{a_1,\ldots,a_n\}$ . Crio uma instância do meu problema da seguinte maneira:

b = n / 2

$b=n/2$ (Eu suponho que

n

$n$ é par),

c = \sum_{i = 1}^{n} a_{i} / 2

$c=\sum_{i=1}^na_i/2$ e a matriz é dada por

[\begin{matrix} a_{1} & \dots & a_{n} \\ a_{1} & \dots & a_{n} \end{matrix}]

$\begin{bmatrix}a_1 & \ldots & a_n\\ a_1 & \ldots & a_n\end{bmatrix}$ . 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

$n/2$ maior não negativo

a_{i}

$a_i$ s e veja se eles somam pelo menos

\sum_{i} a_{i} / 2

$\sum_i a_i/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

@Yuval. A matriz tem entradas não negativas, não é?

Zighalo

Ah - eu perdi essa condição. Mas talvez a redução possa ser ajustada de alguma forma.

Yuval Filmus

@Brika Não necessariamente. A ideia funciona se modificada adequadamente.

Yuval Filmus