NP-dureza de un caso especial de Particionamiento de números

12

Considere el siguiente problema,

  • Dado un conjunto de números positivos { a 1 , ... , a n } en el que k ≥ 3 es una constante, queremos dividir el conjunto en m subconjuntos de tamaño k para que el producto de la suma de cada subconjunto Está maximizado.n=km{a1,…,an}k≥3mk

El problema es bastante similar al conocido particionamiento de números -way, excepto que tenemos un límite en el número de números en cada partición. Para k = 2 se puede proponer el siguiente algoritmo polinómico simple:mk=2

  • suponga que los números están ordenados, es decir, . Luego, para i ≤ m asigne un i al subconjunto i , para i > m , asígnelo al subconjunto n - i + 1 .a1<a2<...<ani≤maiii>mn−i+1

No es difícil ver por qué funciona el algoritmo. Simplemente elija dos contenedores arbitrarios. Cualquier cambio en los números no aumentará la cantidad del producto.

Pero para las más grandes , me pregunto si el problema puede resolverse en tiempo polinómico o no. También estaría agradecido si alguien puede demostrar que es np-hardness.k

Nota: Encontré el problema mientras trabajaba en un problema de programación en redes inalámbricas. Encontré un buen algoritmo heurístico para resolver el problema. Pero después de un tiempo pensé que el problema podría ser teóricamente interesante.

cc.complexity-theory np-hardness application-of-theory polynomial-time Helio
fuente
2
Hmm Me interesaría ver su algoritmo polinómico simple para . k=2
mjqxxxx
2
@Mohsen, gracias. Sugeriría que incluya estos comentarios sobre la motivación, los antecedentes y lo que sabe sobre el caso k = 2 en la pregunta. Eso probablemente lo haría más interesante para los demás.
Kaveh
44
Mi intuición es que el producto de la suma de cada subconjunto se maximiza cuando las sumas son iguales o la diferencia máxima por pares es mínima. Bajo esta suposición, obtenemos una reducción fácil de 3 particiones, que es NP completa (para k = 3).
Mohammad Al-Turkistany
3
(Eliminé dos comentarios que publiqué hace unas horas para reescribirlos con mayor precisión). Como sugirió turkistany, el problema de la partición k es reducible a este problema y, por lo tanto, este problema es NP-difícil para cada k≥3 constante. La única propiedad relevante es que el máximo del producto de las sumas es al menos (∑a_i / k) ^ m si y solo si los números pueden dividirse en m conjuntos cada uno con un tamaño k cuyas sumas son todas iguales. La partición no siempre maximiza el producto, lo que minimiza la diferencia máxima por pares, pero eso es irrelevante siempre que consideremos el problema exacto. (más)
Tsuyoshi Ito
3
(continuación) Si necesita que la entrada sea un conjunto en lugar de un conjunto múltiple , esta reducción aún funciona porque el problema de partición k sigue siendo NP completo incluso con un conjunto, pero tenga cuidado porque la prueba estándar de la integridad de NP del problema de 3 particiones funciona solo cuando se permite que la entrada contenga el mismo entero más de una vez. Consulte Complejidad computacional del problema de 3 particiones con números distintos (precaución: autopromoción).
Tsuyoshi Ito

Respuestas:

11

(Esta es una versión un poco más detallada de mis comentarios sobre la pregunta).

Como turkistany sugirió en un comentario sobre la pregunta, este problema es NP-difícil para cada constante k ≥3 por una reducción del problema de la partición k . La reducción no cambia las instancias en absoluto: solo tenga en cuenta que el máximo del producto de las sumas es al menos (∑ a i / k ) m si y solo si los números se pueden dividir en m conjuntos cada uno con un tamaño k cuyas sumas son todos iguales

Tenga en cuenta que la entrada al problema de partición k generalmente se define como números de km que pueden no ser del todo distintos , y esto es esencial en la prueba estándar de su integridad NP (como la de Garey y Johnson ). Por lo tanto, la reducción anterior solo prueba la dureza NP de una ligera generalización del problema actual en el que se permite que la entrada sea un conjunto múltiple en lugar de un conjunto. Sin embargo, este vacío puede llenarse porque el problema de la partición k sigue siendo NP completo incluso si se requiere que los números en la entrada sean todos distintos; ver [HWW08] para el caso de k = 3 (ver también la respuesta de Serge Gaspersa otra pregunta), que puede modificarse fácilmente para valores mayores de k .

Además, todo lo indicado aquí sigue siendo NP-completo / NP-duro incluso cuando los números en la entrada se dan en unario.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Realizaciones multigráficas de secuencias de grados: la maximización es fácil, la minimización es difícil. Cartas de investigación de operaciones , 36 (5): 594–596, septiembre de 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004

Tsuyoshi Ito
fuente