NP-dureza de un problema de optimización

8

Mientras estudiaba un problema en la teoría algorítmica de juegos, me interesó la complejidad de la siguiente pregunta de optimización:

Problema

Dado:

  • conjunto de tierra dado por ,nU=[n]={1,,n}n
  • m clasificaciones dadas como órdenes totales donde ( ),S iU 1 i mSi,σiSiU1im
  • vector de peso para dado por .w R nUwRn

Objetivo: encontrar un subconjunto maximizando la siguiente suma: donde es el elemento mejor clasificado en según .r ( L ) = i [ m ] , S iL w ( t i ( L ) ) t i ( L ) L S i σ iLU

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

Sospecho que el problema es -hard. De hecho, el problema parece ser difícil incluso cuando todos los son de tamaño . Sin embargo, no he podido probar esto.S i 2NPSi2

Lo que yo sé

Es fácil ver que las siguientes restricciones facilitan el problema:

  • Todos los pesos son uniformes: seleccionar todos los elementos es claramente óptimo.
  • todas las clasificaciones son clasificaciones completas sobre : la mejor solución se obtiene tomando el elemento con el peso máximo.U
  • los pesos son solo binarios ( ), luego seleccionar todos los elementos de pesaje 1 es óptimo.w{0,1}n1

Sin embargo, no he podido encontrar un algoritmo de tiempo polinómico para el caso general (por ejemplo, usando LP). Por otro lado, probar que el problema es -duro no parece fácil. La estructura de las instancias del problema no permite la codificación fácil de otros problemas. (Tenga en cuenta que la dureza del problema vendrá de usar la misma L para todas las órdenes parciales, sin embargo, usar el mismo vector de peso para todas ellas hace que la dureza de prueba no sea sencilla). He intentado sin éxito reducir algunos problemas duros de N P como Subset-Sum, NAND-Circuit-SAT, etc. a la versión de decisión de este problema (¿hay un subconjunto tal que r ( L ) k )?NPLNPr(L)k

Una IP coincidente se puede construir silenciosamente fácilmente para una instancia determinada del problema, pero no veo ningún parecido suficiente con ningún problema que conozca.

Pregunta

¿Conoces la complejidad de este problema? ¿Hay alguna referencia que estudie la complejidad de problemas de optimización similares? ¿Cómo probarías que este problema de optimización es -duro? (Si es realmente difícil).NP

JoelO
fuente
2
Creo que su solución es correcta y si usa un truco similar para las cláusulas, incluso puede restringir cada Si a 2 elementos.
domotorp

Respuestas:

8

Bueno, aquí hay una posible solución:

La reducción será de 3SAT.

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

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

Crea dos 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
fuente