Nummernvergabe

Wenn Zahlen so dass ist, gibt es eine Zuordnung der Zahlen ist eine Permutation von so dass $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$

Ich kann keinen effizienten Algorithmus finden und das löst dieses Problem. Es scheint ein kombinatorisches Problem zu sein. Ich konnte kein ähnliches NP-Complete-Problem finden. Sieht dieses Problem wie ein bekanntes NP-Complete-Problem aus oder kann es mit einem Polynomalgorithmus gelöst werden?

np-complete decision-problem gprime
quelle

Haben Sie bei dem Problem Fortschritte erzielt?

Yuval Filmus

Ich habe vergessen zu erwähnen, dass

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

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

gprime

Zugehöriges Problem , auch ohne zufriedenstellende Antwort. (Es mag auf den ersten Blick nicht klar sein, wie sie zusammenhängen, aber wenn , entspricht das Problem dem Finden einer Permutation von so dass .

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

Antworten:

Dieses Problem ist stark NP-vollständig.

Angenommen, alle sind ungerade. Dann wissen wir, dass, da ungerade ist, einer von und gerade und der andere ungerade ist. Wir können annehmen, dass ungerade und ist. Indem und , können wir zeigen, dass dies äquivalent zu ist Fragen nach zwei Permutationen und der Zahlen so dass . $A_j$ $i_{2j-1} + i_{2j} = A_j$ $i_{2j-1}$ $i_{2j}$ $i_{2j-1}$ $i_{2j}$ $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ $\sigma_j = \frac{1}{2}(i_{2j})$ $\pi$ $\sigma$ $1 \ldots n$ $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$

Es ist bekannt, dass dieses Problem NP-vollständig ist. siehe dieses cstheory.se-Problem und dieses Papier von W. Yu, H. Hoogeveen und JK Lenstra, auf das in der Antwort verwiesen wird.

Peter Shor
quelle

Hier ist ein Hinweis für den Einstieg: Da die Summe aller Zahlen von bis genau , ist eine Lösung nur möglich, wenn tatsächlich , usw. . wir also haben, kennen wir und so weiter. Auch . $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
quelle

Wie soll ich also zunächst wählen ? Ich sehe die Lösung nicht. Aber danke für die Eigenschaft

i_{1}

$i_1$

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

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

gprime

Wenn die sortiert sind, kennen wir , , und so weiter. Reichen diese Kriterien zusammen mit aus? Wenn dies der Fall ist, gibt es möglicherweise einen einfachen Algorithmus für dieses Problem.

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

Ja, sie sind sortiert. Ich werde versuchen, dies zu verwenden ...

Gprime

@PeterShor Sie müssen auch Grenzwerte aus der entgegengesetzten Richtung berücksichtigen, z. B. usw. Wenn man das Problem anekdotisch betrachtet, scheint es, dass ein einfacher gieriger Algorithmus Lösungen finden sollte, wenn sie existieren, und genau dann scheitern sollte, wenn sie es nicht tun - aber ich habe Probleme, es zu beweisen.

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: Du sprichst einen guten Punkt an. Tatsächlich implizieren die Grenzen aus einer Richtung auch die Grenzen aus der anderen, aber das ist auf den ersten Blick überhaupt nicht offensichtlich. Ich habe mir ein ähnliches Problem angesehen und konnte keinen einfachen Algorithmus finden (aber es sah für mich auch so aus, als ob das Analogon dieser Kriterien tatsächlich ausreicht).

Peter Shor

Es ist ein Matching-Problem und kann daher mit Edmonds Algorithmus gelöst werden. Siehe Wikipedia

Wille
quelle

Die Idee von Stackexchange ist es, ein Q & A zu haben, das so vollständig wie möglich ist. Könnten Sie Ihre Antwort erweitern, um mehr als nur ein Link zu Wikipedia zu sein?

Luke Mathieson

Können Sie das näher erläutern? Ich sehe nicht ein, wie ich diese Algorithmen verwenden kann, um meine Frage zu lösen.

Gprime

Eigentlich sieht es für mich wie ein Sonderfall von 3-Matching aus, der NP-vollständig ist. Dies bedeutet nicht, dass das OP-Problem NP-vollständig ist.

Peter Shor

Könnte es vielleicht ein zweiteiliges Matching sein? Ich werde in die 3-Übereinstimmung schauen, um zu sehen, ob ich es herausfinden kann. Vielen Dank!

Gprime