Rompecabezas de palos de corte

18

Problema: se nos da un conjunto de palos que tienen longitudes enteras. La suma total de sus longitudes es n (n + 1) / 2.

¿Podemos separarlos para obtener palos de tamaño en tiempo polinómico? 1,2,...,norte

Sorprendentemente, la única referencia que encuentro para este problema es esta antigua discusión:

http://www.iwriteiam.nl/cutsticks.html

¿Qué más se sabe sobre el problema? ¿Podemos demostrar que el problema está "en el limbo"?

Actualización: El problema de los palos de corte tiene la restricción de que cada palo tiene al menos unidades de longitud. (Vea los comentarios y la respuesta de Tsuyoshi para el caso sin restricciones).norte

Jagadish
fuente
1
La formulación del problema en el enlace que proporcionó tiene el siguiente requisito adicional, con el cual el problema parece tener más sentido: "Ninguno de los palos es más corto que ". norte
Jukka Suomela
Es un problema no resuelto determinar si esto siempre es posible.
Emil
@Emil: ¿Tienes una referencia? ¿Algo más reciente que la antigua discusión (1995) vinculada en el OP?
Jukka Suomela
@ Jukka Mi error. Olvidé mencionar ese punto ya que tenía la impresión de que el problema no cambiará significativamente con esa restricción. De todos modos, estoy feliz ya que la respuesta de Tsuyoshi ha generado una pregunta interesante.
Jagadish
Este es un problema bastante bueno, pero el título es engañoso. Sugiere que este es un problema de teoría de la complejidad, cuando en realidad es un rompecabezas de algoritmos genial al igual que el problema de barajar. Tal vez deberías reformular el título.
Suresh Venkat

Respuestas:

16

Precaución: como comentó Jukka Suomela sobre la pregunta, la página vinculada desde la pregunta trata sobre un problema diferente del problema establecido en la pregunta, ya que el problema en la página tiene una restricción de que la longitud de los palos dados es mayor o igual a norte. Esta respuesta es sobre el problema sin esta restricción. Dado que el comentario de Emil sobre la pregunta se refiere al problema con la restricción, no hay contradicción entre su comentario y la siguiente respuesta.


El problema es NP-completo, incluso si los números se dan en unario.

El problema de 3 particiones es el siguiente:
Instancia : enteros positivos a 1 , ..., a n en unario, donde n = 3m y la suma de los n enteros es igual a mB, de modo que cada a i satisface B / 4 < a i <B / 2.
Pregunta : ¿Pueden los enteros a 1 , ..., a n dividirse en m conjuntos múltiples para que la suma de cada conjunto múltiple sea igual a B?

El problema de 3 particiones es NP-completo incluso si un 1 , ..., un n son todos distintos [HWW08] (gracias a Serge Gaspers por informarme sobre esto ). Es posible reducir esta versión restringida del problema de 3 particiones al problema en cuestión de la siguiente manera.

Supongamos que se nos da una instancia del problema de 3 particiones que consiste en enteros positivos distintos a 1 , ..., a n . Sea m = n / 3 y B = (a 1 +… + a n ) / m, y sea N el máximo entre a i . Considere la siguiente instancia del problema del palo: la instancia consiste en un palo de longitud k por cada k∈ {1, ..., N} ∖ {a 1 , ..., a n } ym palos de longitud B. Usando el hecho que cada a i satisface a i > B / 4 ≥ N / 2, es fácil demostrar que este problema de palo tiene solución si y solo si la instancia del problema de 3 particiones tiene solución.

Referencias

[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
3
No sé si el problema de 3 particiones sigue siendo NP completo o no si los números son distintos, y estoy preguntando al respecto: cstheory.stackexchange.com/questions/716/…
Tsuyoshi Ito
Serge Gaspers me dijo que sí (¡gracias!). Simplifiqué la prueba usándolo.
Tsuyoshi Ito