Ya publiqué esta pregunta hace un tiempo en MathOverflow , pero que yo sepa, todavía está abierta, así que la vuelvo a publicar aquí con la esperanza de que alguien haya oído hablar de ella.
Planteamiento del problema
Supongamos que , y son tres particiones en partes no vacías (denotadas por 's, ' s y 's) del conjunto { }. Encuentre dos permutaciones y que minimicenQ R p P h Q i R j 1 , 2 , … , n π σ p ∑ i = 1 | P i ∪ Q π i ∪ R σ i | .
Preguntas
1) ¿Cuál es la complejidad de este problema (o del problema de decisión correspondiente)?
2) Si el problema se puede resolver en tiempo polinómico, ¿sigue siendo cierto para cualquier número de particiones?
Trabajo previo
Berman, DasGupta, Kao y Wang ( http://dx.doi.org/10.1016/j.ipl.2007.06.008 ) estudian un problema similar para particiones, pero usando pairwise 's en lugar de en lo anterior suma. Demuestran que el problema es MAX-SNP-hard para , incluso cuando cada parte tiene solo dos elementos, al reducir MAX-CUT en gráficos cúbicos a un caso especial de su problema, y dan un -proximación para cualquier . Hasta ahora, no he podido encontrar mi problema en la literatura ni adaptar su prueba.Δ ∪ k = 3 ( 2 - 2 / k ) k
Subcasas fáciles
Aquí hay algunas subcajas que he descubierto que pueden resolverse en tiempo polinómico:
- el caso ;
- el caso , para cualquier ;k
Además, cuando , no hay dos partes iguales y todas las partes tienen un tamaño , tenemos el límite inferior (no sé si está ajustado).2 3 p + 1
fuente