Dureza NP de um problema de otimização

8

Enquanto estudava um problema na teoria algorítmica dos jogos, fiquei interessado na complexidade da seguinte pergunta de otimização:

Problema

Dado:

  • conjunto de base dado por n ,U=[n]={1,,n}n
  • classificação dada como ordens totaisS i , σ i onde S iL ( 1 i m ),mSi,σiSiU1im
  • vetor de peso para dado por w R n .UwRn

Meta: encontrar um subconjunto maximizar a seguinte soma: r ( G ) = Σ i [ m ] , S iL w ( t i ( L ) ) , onde t i ( L ) é o mais alto ponto classificados em L S i de acordo com σ i .LU

r(L)=i[m], SiLw(ti(L))
ti(L)LSiσi

I suspeitar que o problema é -Hard. Na verdade o problema parece ser difícil mesmo quando todos o S i 's são de tamanho 2 . No entanto, não fui capaz de provar isso.NPSi2

O que eu sei

É fácil ver que as seguintes restrições facilitam o problema:

  • todos os pesos são uniformes: a seleção de todos os elementos é claramente ideal.
  • todas as classificações são classificações completas sobre : a melhor solução é obtida pegando o elemento com o peso máximo.U
  • os pesos são apenas binários ( ), então a seleção de todos os elementos com peso 1 é ideal.w{0,1}n1

NPLNPr(L)k

Um IP correspondente pode ser construído silenciosamente facilmente para uma determinada instância do problema, mas não vejo nenhuma semelhança suficiente com nenhum problema que eu conheça.

Questão

NP

JoelO
fonte
2
Acho que sua solução está correta e, se você usar um truque semelhante para as cláusulas, poderá até restringir cada Si a 2 elementos.
Domotorp #

Respostas:

8

Bem, aqui está uma solução possível:

A redução será da 3SAT.

m(φ1,,φm)n(x1,,xn)

xi,x¯iTruexit{xi,x¯i}i=1,,n1t1.5

Crie dois conjuntos de consumidores:

x1,,xn{xi,x¯i}Truei=1,,n

σi1:xitσi2:x¯itσi3:xix¯iσi4:xix¯i

txix¯i434.5

φj=j1i2j3σj:j1>j2>j3φjj1,j2j31σj

m+4.5n

JoelO
fonte