Dureza NP de um caso especial de particionamento de números

12

Considere o seguinte problema,

  • Dado um conjunto de números positivos { a 1 , … , a n } em que k ≥ 3 é uma constante, queremos particionar o conjunto em m subconjuntos de tamanho k, para que o produto da soma de cada subconjunto é maximizado.n=km{a1,…,an}k≥3mk

O problema é bastante semelhante ao conhecido particionamento de número way, exceto que temos um limite no número de números em cada partição. Para k = 2, o seguinte algoritmo polinomial simples pode ser proposto,mk=2

  • assumem os números são classificadas, ou seja, . Então, para i ≤ m atribua um i ao subconjunto i , para i > m , atribua-o ao subconjunto n - i + 1 .a1<a2<...<ani≤maiii>mn−i+1

Não é difícil ver por que o algoritmo funciona. Basta escolher duas caixas arbitrárias. Qualquer troca nos números não aumentará a quantidade do produto.

Mas para maiores , fico imaginando se o problema pode ser resolvido em tempo polinomial ou não? Eu também ficaria agradecido se alguém pudesse mostrar sua dureza np.k

Nota: Encontrei o problema enquanto trabalhava em um problema de agendamento em redes sem fio. Encontrei um bom algoritmo heurístico para resolver o problema. Mas depois de um tempo, pensei que o problema poderia ser teoricamente interessante.

cc.complexity-theory np-hardness application-of-theory polynomial-time Hélio
fonte
2
k=2
2
@ Ohhsen, obrigado. Sugiro que você inclua esses comentários sobre motivação, histórico e o que você sabe sobre o caso k = 2 na pergunta. Isso provavelmente tornaria mais interessante para os outros.
Kaveh
4
Minha intuição é que o produto da soma de cada subconjunto seja maximizado quando as somas forem iguais ou a diferença máxima por pares for mínima. Sob essa suposição, obtemos fácil redução da partição tripla, que é NP-completa (para k = 3).
Mohammad Al-Turkistany
3
(Eu removi dois comentários que publiquei algumas horas atrás para reescrevê-los com mais precisão.) Como sugerido pelo turquia, o problema da partição k é redutível a esse problema e, portanto, esse problema é difícil de NP para cada constante k≥3. A única propriedade relevante é que o máximo do produto das somas é de pelo menos (∑a_i / k) ^ m se, e somente se, os números puderem ser particionados em conjuntos de m, cada um com o tamanho k, cujas somas são iguais. O produto nem sempre é maximizado pela partição, o que minimiza a diferença máxima entre pares, mas isso é irrelevante enquanto considerarmos o problema exato. (mais)
Tsuyoshi Ito
3
(continuação) Se você exigir que a entrada seja um conjunto em vez de um conjunto múltiplo , essa redução ainda funcionará porque o problema da partição k permanece NP completo mesmo com um conjunto, mas tenha cuidado porque a prova padrão da completude NP O problema das 3 partições funciona apenas quando é permitido que a entrada contenha o mesmo número inteiro mais de uma vez. Consulte Complexidade computacional do problema de 3 partições com números distintos (cuidado: autopromoção).
Tsuyoshi Ito

Respostas:

11

(Esta é uma versão um pouco mais detalhada dos meus comentários sobre a questão.)

Como o Turquistão sugeriu em um comentário sobre a questão, esse problema é NP-difícil para cada constante k ≥3 por uma redução do problema da partição- k . A redução não altera as instâncias: observe que o máximo do produto das somas é de pelo menos (∑ a i / k ) m se e somente se os números puderem ser particionados em m conjuntos cada um com o tamanho k cujas somas são Tudo igual.

Observe que a entrada para o problema da partição k é geralmente definida como números de km que podem não ser totalmente distintos , e isso é essencial na prova padrão de sua completude NP (como a de Garey e Johnson ). Portanto, a redução acima prova apenas a dureza NP de uma ligeira generalização do problema atual, onde é permitido que a entrada seja um multiset em vez de um conjunto. No entanto, essa lacuna pode ser preenchida porque o problema da partição k permanece NP-completo, mesmo que seja necessário que os números na entrada sejam todos distintos; veja [HWW08] para o caso de k = 3 (veja também a resposta de Serge Gasperspara outra pergunta), que pode ser modificada facilmente para valores maiores de k .

Além disso, tudo o que é declarado aqui permanece NP-completo / NP-rígido, mesmo quando os números na entrada são dados unários.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Realizações multigráficas de seqüências de graus: a maximização é fácil, a minimização é difícil. Letters , 36 (5): 594–596, setembro de 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004

Tsuyoshi Ito
fonte