Problema de otimização de conjunto - é np-complete?

10

O conjunto é fornecido. Para cada elemento , temos peso e custo . O objetivo é encontrar o subconjunto de tamanho que maximize a seguinte função objetivo: .S={e1,,en}eiwi>0ci>0Mk

eiMwi+eiMwicieiMci

O problema é NP-difícil?

Como a função objetivo parece estranha, é útil explicar uma aplicação da função objetivo.

Suponha que tenhamos n itens a e que haja cópias de cada objeto em nosso inventário. Temos alguns clientes e eles estão interessados ​​nesses objetos na proporção do seu peso , o que significa que o objeto com maior é mais popular. Temos um sistema de venda on-line e precisamos responder às solicitações de nossos clientes corretamente. Não podemos reconhecer objetos por suas formas (todos parecem iguais!). Mas temos algum classificador para encontrá-los. Cada classificador pode ser usado para detectar cópias de um objeto. Nosso objetivo é executar o classificador k, a fim de maximizar a satisfação de nossos clientes.e1encieiwiwi

PS: Pode ser útil pensar no caso em que para todos os ; no entanto, não tenho certeza. [ Eu estava errado sobre isso! Está em P por esta suposição ]wici=pin

Nasooh
fonte
O termo certo é menor ou igual ao maior peso de um elemento que não esteja em M. Portanto, se você tem um elemento com um grande peso, é melhor colocá-lo em M, em vez de deixá-lo desperdiçar. Portanto, M deve consistir nos elementos com os k maiores pesos. Direita?
Zotachidil
Não está correto, porque os custos também são importantes. Considere o seguinte exemplo:
Nasooh
w1 = 50, c1 = 80 - w2 = 40, c2 = 15 - w3 = 10, c3 = 5. Para k igual a 1, escolher e2 é mais benéfico que e1.
Nasooh
Você está certo. Hmm ...
zotachidil
2
Obrigado por tentar explicar a motivação. Infelizmente, a conexão entre sua explicação e a função objetivo da pergunta ainda não está totalmente clara para mim, mas acho que tenho que estar satisfeito com a explicação atual para manter a pergunta dentro de um prazo razoável.
Tsuyoshi Ito

Respostas:

2

A resposta abaixo observa que um caso especial do problema é solucionável em tempo polinomial. Isso não responde totalmente à pergunta no post, mas pode fornecer algumas dicas sobre o que pode ser necessário para uma prova de dureza NP e provocar um interesse adicional no post ...

Observação. O problema no post tem um algoritmo que, dada qualquer instância em que cada é um número inteiro, é executado no polinômio do tempo em e . n D = Σ i c icinD=ici

Esboço de prova. Corrija qualquer entrada que e (WLOG) . Reformulando um pouco o problema, o objetivo é encontrar de tamanho maximizando .w , c R n + S = { 1 , 2 , , n } M S K i M w i c i(S,w,c,K)w,cR+nS={1,2,,n}MSKiMwiciiMciiMwi

Considere o seguinte programa dinâmico. Para quaisquer números inteiros com , e , defina A solução desejada é .(d1,d2,k,m)0d1d2D0kKkmn

ϕ(d1,d2,k,m)=max{iMwi(ci/d11) : M[m],|M|=k,iMci=d2}.
maxdϕ(d,d,K,n)

Particionando as possíveis soluções para naquelas que contêm e naquelas que não contêm , obtemos a recorrência Deixamos os casos de fronteira como um exercício.ϕ(d1,d2,k,m)m

ϕ(d1,d2,k,m)=max{ϕ(d1,d2cm,k1,m1)+wm(cm/d11)ϕ(d1,d2,k,m1).

O número de sub-problemas é , e para cada lado da mão direita da recorrência pode ser avaliada em tempo constante, de modo que o algoritmo é executado em tempo polinomial em e . O(n2D2)nD  

Corolário. A menos que P = NP, qualquer redução que mostre a dureza NP será reduzida para instâncias em que não é polinomial em .Dn

Observação. A menos que eu esteja enganado, também há um PTAS para o problema no post, com base no arredondamento dos 's e usando programação dinâmica. No entanto, a existência de um PTAS não tem relação direta com a dificuldade do NP, conforme solicitado no post.wi

Também estou curioso --- alguém sabe se o caso especial quando (para cada ) tem um algoritmo de poli-tempo? (EDIT: sim, pelo comentário de Willard Zhan, isso parece ser otimizado ao usar para conter os maiores elementos.)wi=ciiMk

Neal Young
fonte
11
Não é o caso de o mesmo que minimizar , que é otimizado quando consiste no maior é? wi=ci(ijMwiwj)/(iMwi)Mwi
Willard Zhan
@WillardZhan, sim, isso parece certo.
Neal Young
-6

Você está perguntando sobre a maximização de uma função sem restrições?

É realmente simples. Se M é o maior conjunto, então é a melhor solução. Não há necessidade de calcular nada.

Esse problema parece semelhante ao problema da mochila, que é NP por sinal.

Guillermo.
fonte
3
A pergunta diz: "o subconjunto M de tamanho k".
Tsuyoshi Ito