NP-твердость частного случая нумерации

Рассмотрим следующую проблему:

Учитывая набор из положительных чисел в которых является константой, мы хотим разбить набор на подмножеств размера так, чтобы произведение суммы каждого подмножества максимально $n = k m$ $\{ a_1, \dots, a_n \}$ $k \ge 3$ $m$ $k$

Эта проблема очень похожа на хорошо известное разбиение номеров way, за исключением того, что у нас есть ограничение на число номеров в каждом разделе. Для может быть предложен следующий простой полиномиальный алгоритм, $m$ $k = 2$

предположим, что числа отсортированы, то . Затем для назначьте подмножеству , для назначьте его подмножеству . $a_1<a_2<...<a_n$ $i≤m$ $a_i$ $i$ $i>m$ $n−i+1$

Нетрудно понять, почему алгоритм работает. Просто выберите две произвольные корзины. Любой обмен числами не приведет к увеличению количества товара.

Но для больших я задаюсь вопросом, может ли проблема быть решена за полиномиальное время или нет? Я был бы также благодарен, если бы кто-то мог показать это нп-твердость. $k$

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

cc.complexity-theory np-hardness application-of-theory polynomial-time гелий
источник

k = 2

$k=2$

@ Мохсен, спасибо. Я бы посоветовал вам включить в вопрос эти комментарии о мотивации, предыстории и том, что вы знаете о случае k = 2. Это, вероятно, сделает его более интересным для других.

Каве

Моя интуиция заключается в том, что произведение суммы каждого подмножества максимизируется, когда суммы равны или максимальная парная разница минимальна. В этом предположении мы получаем легкое сокращение от 3-разбиения, являющегося NP-полным (для k = 3).

Мухаммед Аль-Туркистани

(Я удалил два комментария, которые я разместил несколько часов назад, чтобы переписать их более точно.) Как предположил Туркистани, проблема k-разбиения сводится к этой проблеме, и поэтому эта проблема NP-трудна для каждой константы k≥3. Единственное релевантное свойство заключается в том, что максимум произведения сумм составляет не менее (∑a_i / k) ^ m тогда и только тогда, когда числа можно разбить на m множеств, каждый из которых имеет размер k, у которого все суммы равны. Произведение не всегда максимизируется разделением, которое минимизирует максимальную попарную разницу, но это не имеет значения, пока мы рассматриваем точную проблему. (подробнее)

Цуёси Ито

(продолжение) Если требуется, чтобы входные данные были набором, а не мультимножеством , это сокращение по-прежнему работает, поскольку проблема k-разбиения остается NP-полной даже с набором, но будьте осторожны, поскольку стандартное доказательство NP-полноты проблема с 3 разделами работает только тогда, когда входные данные могут содержать одно и то же целое число более одного раза. См. Вычислительная сложность задачи с 3 разделами с различными числами (осторожно: самореклама).

Цуёси Ито

(Это немного более подробная версия моих комментариев по этому вопросу.)

Как Туркистани предложил в комментарии к вопросу, эта проблема является NP-трудной для каждой константы k ≥3 путем сокращения от проблемы k- разбиения. Сокращение не меняет экземпляров вообще: просто обратите внимание, что максимум произведения сумм составляет, по крайней мере, ( _i a _i / k ) ^m тогда и только тогда, когда числа могут быть разбиты на m множеств, каждый из которых имеет размер k , суммы которого равны все равны.

Обратите внимание, что входные данные для проблемы k- разбиения обычно определяются как числа км, которые могут быть не все различны , и это важно в стандартном доказательстве его NP-полноты (например, в Garey и Johnson ). Таким образом, приведенное выше сокращение лишь доказывает трудность NP небольшого обобщения текущей проблемы, когда вход разрешается быть мультимножеством, а не множеством. Однако этот пробел может быть заполнен, потому что проблема k- разбиения остается NP-полной, даже если требуется, чтобы числа во входных данных были различны; см. [HWW08] для случая k = 3 (см. также ответ Сержа Гасперсана другой вопрос), который можно легко изменить для больших значений k .

Кроме того, все, что здесь указано, остается NP-полным / NP-сложным, даже если числа на входе даны в одинарном виде.

[HWW08] Хизер Хьюлетт, Тодд Дж. Уилл, Герхард Дж. Вёджингер. Мультиграф реализации последовательностей степеней: максимизация проста, минимизация трудна. Письма об исследовании операций , 36 (5): 594–596, сентябрь 2008 г. http://dx.doi.org/10.1016/j.orl.2008.05.004

Цуёси Ито
источник

NP-твердость частного случая нумерации

Ответы: