Asignación de números

Dados números modo que hay una asignación de números que es una permutación de tal que $k$ $A_1 \leq A_2 \leq ... \leq A_k$ $\sum\limits_{i=1}^k A_i = k(2k + 1)$ $i_1, i_2, ... , i_{2k}$ $1, 2, ... , 2k$

$i_1 + i_2 \leq A_1\\ i_3 + i_4 \leq A_2\\ .\\.\\.\\ i_{2k-1} + i_{2k} \leq A_k$

No puedo encontrar un algoritmo eficiente y eso resuelve este problema. Parece ser un problema combinatorio. No pude encontrar un problema NP-Complete similar. ¿Este problema se parece a un problema NP-Complete conocido o se puede resolver con un algoritmo polinomial?

np-complete decision-problem gprime
fuente

¿Has progresado en el problema?

Yuval Filmus

Olvidé mencionar que

A_{1} \leq A_{2} \leq . . . \leq A_{k}

$A_1 \leq A_2 \leq ... \leq A_k$

gprime

Problema relacionado , también sin una respuesta satisfactoria. (Puede que no esté claro a primera vista cómo están relacionados, pero si , el problema es equivalente a encontrar una permutación de para que .

K = 2 N

$K=2N$

1 \dots 2 N

$1 \ldots 2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a-1} - i_{2a} = A_i$

Peter Shor

Respuestas:

Este problema es fuertemente NP-completo.

Supongamos que todas las son impares. Entonces sabemos que dado que es impar, uno de e es par y el otro es impar. Podemos suponer que es impar y que es par. Al permitir que $A_j$ $i_{2j-1} + i_{2j} = A_j$ $i_{2j-1}$ $i_{2j}$ $i_{2j-1}$ $i_{2j}$ y $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ , podemos mostrar que esto es equivalente a pedir dos permutaciones,y, de los númerosmodo que $\sigma_j = \frac{1}{2}(i_{2j})$ $\pi$ $\sigma$ $1 \ldots n$ . $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Se sabe que este problema es NP-completo; vea este problema cstheory.se y este artículo de W. Yu, H. Hoogeveen y JK Lenstra referenciados en la respuesta.

Peter Shor
fuente

Aquí hay una pista para comenzar: dado que la suma de todos los números del al es exactamente , una solución es posible solo si de hecho , y así sucesivamente. Así dieron que sé , y así sucesivamente. Además, . $1$ $2k$ $k(2k+1)$ $i_1 + i_2 = A_1$ $i_3 + i_4 = A_2$ $i_1$ $i_2$ $3 \leq A_j \leq 4k-1$

Yuval Filmus
fuente

Entonces, ¿cómo debo elegir

para empezar? No estoy viendo la solución. Pero gracias por la propiedad

i_{1}

$i_1$

3 \leq A_{j} \leq 4 k - 1

$3 \leq A_j \leq 4k -1$

gprime

Si el

está ordenado, sabemos

, y así sucesivamente. Son estos criterios, junto con

, suficiente? Si lo son, posiblemente podría haber un algoritmo simple para este problema.

A_{i}

$A_i$

3 \leq A_{1}

$3 \leq A_1$

10 \leq A_{1} + A_{2}

$10 \leq A_1 + A_2$

21 \leq A_{1} + A_{2} + A_{3}

$21 \leq A_1 + A_2 + A_3$

\sum_{i} A_{i} = k (2 k + 1)

$\sum_i A_i = k(2k+1)$

Peter Shor

Sí, están ordenados. Trataré de usar esto ...

gprime

@PeterShor También debe considerar los límites desde la dirección opuesta, es decir,

, y así sucesivamente. Si analizamos el problema de forma anecdótica, parece que un algoritmo codicioso simple debería descubrir soluciones cuando existen y fallar precisamente cuando no existen, pero tengo problemas para demostrarlo.

4 n - 1 \geq A_{n}, 8 n - 6 \geq A_{n - 1} + A_{n}

$4n-1 \geq A_n, 8n-6 \geq A_{n-1}+A_{n}$

torquestomp

@torquestomp: Estás planteando un buen punto. De hecho, los límites de una dirección también implican los límites de la otra, pero eso no es nada obvio a primera vista. Observé un problema similar y no pude encontrar un algoritmo simple (pero también me pareció que el análogo de estos criterios era suficiente).

Peter Shor

Es un problema de coincidencia, por lo que puede resolverse utilizando el algoritmo de Edmond. Ver wikipedia

Será
fuente

La idea de Stackexchange es tener un Q&A que sea lo más completo posible. ¿Sería capaz de ampliar su respuesta para que sea más que un simple enlace a wikipedia?

Luke Mathieson,

¿Puedes elaborar? No veo cómo puedo usar esos algoritmos para resolver mi pregunta.

gprime

En realidad, para mí parece un caso especial de 3 coincidencias, que es NP completo. Esto no significa que el problema de los PO esté completo en NP.

Peter Shor

¿Podría ser quizás una coincidencia bipartita? Examinaré la combinación de 3 para ver si puedo resolverlo. ¡Gracias!

gprime