Attribution de numéros

Étant donné nombres tel que est - il une attribution de numéros qui est une permutation de $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}$ tel que $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$

Je ne trouve pas d'algorithme efficace et cela résout ce problème. Cela semble être un problème combinatoire. Je n'ai pas pu trouver un problème NP-Complete similaire. Ce problème ressemble-t-il à un problème NP-Complete connu ou peut-il être résolu avec un algorithme polynomial?

np-complete decision-problem gprime
la source

Avez-vous fait des progrès sur le problème?

Yuval Filmus

J'ai oublié de mentionner que

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

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

gprime

Problème connexe , également sans réponse satisfaisante. (Il peut ne pas être clair à première vue comment ils sont liés, mais si

, le problème équivaut à trouver une permutation de

sorte 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

Réponses:

Ce problème est fortement NP-complet.

Supposons que tous les soient impairs. On sait alors que puisque est impair, l'un de et est pair et l'autre est impair. On peut supposer que est impair et est pair. En laissant $A_j$ $i_{2j-1} + i_{2j} = A_j$ $i_{2j-1}$ $i_{2j}$ $i_{2j-1}$ $i_{2j}$ et $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ , on peut montrer que cela revient à demander deux permutations,et, des nombrestels que $\sigma_j = \frac{1}{2}(i_{2j})$ $\pi$ $\sigma$ $1 \ldots n$ . $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Ce problème est connu pour être NP-complet; voir ce problème cstheory.se et cet article de W. Yu, H. Hoogeveen et JK Lenstra référencé dans la réponse.

Peter Shor
la source

$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
la source

i_{1}

$i_1$

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

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

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)$

Oui, ils sont triés. Je vais essayer d'utiliser ça ...

gprime

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: Vous soulevez un bon point. En fait, les limites d'une direction impliquent également les limites de l'autre, mais ce n'est pas du tout évident à première vue. J'ai regardé un problème similaire et je n'ai pas pu trouver un algorithme simple (mais il me semblait aussi que l'analogue de ces critères était effectivement suffisant).

Peter Shor

C'est un problème de correspondance, et peut donc être résolu en utilisant l'algorithme d'Edmond. Voir wikipedia

Volonté
la source

L'idée de Stackexchange est d'avoir un Q & A aussi complet que raisonnablement possible. Pourriez-vous étendre votre réponse pour être plus qu'un simple lien vers wikipedia?

Luke Mathieson

Peux-tu élaborer? Je n'arrive pas à voir comment je peux utiliser ces algorithmes pour résoudre ma question.

gprime

En fait, pour moi, cela ressemble à un cas spécial de correspondance 3, qui est NP-complet. Cela ne signifie pas que le problème des PO est NP-complet.

Peter Shor

Serait-ce peut-être une correspondance bipartite? Je vais regarder dans le 3-match pour voir si je peux le comprendre. Merci!

gprime