присвоение номера

Для заданных чисел таких что , существует ли присвоение чисел который является перестановкой такой, что $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$

Я не могу найти эффективный алгоритм, и это решает эту проблему. Кажется, это комбинаторная проблема. Мне не удалось найти подобную проблему NP-Complete. Эта проблема выглядит как известная проблема NP-Complete или ее можно решить с помощью полиномиального алгоритма?

np-complete decision-problem Gprime
источник

Достигли ли вы прогресса в решении проблемы?

Юваль Фильмус

Я забыл упомянуть, что

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

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

gprime

Связанная проблема , также без удовлетворительного ответа. (На первый взгляд может быть неясно, как они связаны, но если , проблема эквивалентна нахождению перестановки так что .

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$

Питер Шор

Ответы:

Эта проблема сильно NP-полная.

Предположим, что все нечетны. Тогда мы знаем, что, поскольку нечетно, один из и четный, а другой нечетный. Можно предположить, что нечетно, а четно. Пусть $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)$

Эта проблема, как известно, является NP-полной; см. эту проблему cstheory.se и эту статью W. Yu, H. Hoogeveen и JK Lenstra, на которые даны ссылки в ответе.

Питер Шор
источник

Вот подсказка для начала: поскольку сумма всех чисел от до в точности равна , решение возможно только в том случае, если на самом деле , и так далее. Итак, учитывая, что мы знаем, что , и так далее. Также . $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$

Юваль Фильмус
источник

Так как я должен выбрать

, чтобы начать? Я не вижу решения. Но спасибо за собственность

i_{1}

$i_1$

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

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

gprime

Если

отсортированы, мы знаем

и так далее.

ли этих критериев вместе с

? Если они есть, возможно, существует простой алгоритм для этой проблемы.

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

Питер Шор

Да, они отсортированы. Я постараюсь использовать это ...

gprime

@PeterShor Вы также должны учитывать пределы в противоположном направлении, то есть

и т. Д. И т. Д. Глядя на проблему анекдотично, кажется, что простой жадный алгоритм должен находить решения, когда они существуют, и терпеть неудачу именно тогда, когда их нет - но у меня возникают проблемы с доказательством этого.

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: Вы подняли хороший вопрос. На самом деле, ограничения с одного направления также подразумевают ограничения с другого, но это не так очевидно с первого взгляда. Я посмотрел на похожую проблему и не смог понять простой алгоритм (но мне показалось, что аналога этих критериев действительно было достаточно).

Питер Шор

Это проблема соответствия, и поэтому ее можно решить с помощью алгоритма Эдмонда. Смотрите википедию

Будет
источник

Идея Stackexchange состоит в том, чтобы иметь максимально полные ответы на вопросы. Сможете ли вы расширить свой ответ, чтобы быть больше, чем просто ссылка на Википедию?

Люк Мэтисон

Можете ли вы уточнить? Я не вижу, как я могу использовать эти алгоритмы для решения моего вопроса.

gprime

На самом деле, для меня это выглядит как частный случай 3-соответствия, который является NP-полным. Это не означает, что проблема ОП является NP-полной.

Питер Шор

Может ли это быть двухстороннее соответствие? Я посмотрю на 3-соответствие, чтобы увидеть, смогу ли я понять это. Спасибо!

gprime