Twardość NP specjalnego przypadku podziału na liczby

Rozważ następujący problem,

• Biorąc pod uwagę zestaw dodatnimi liczbami { 1 , ... , n } , w którym K ≥ 3 jest stała, chcemy podzielić wkomponowany m podzbiorów wielkości K , przy czym produkt z sumy każdego podzbioru jest zmaksymalizowane.$n = k m$$\{ a_1, \dots, a_n \}$$k \ge 3$$m$$k$

Problem jest podobny do dobrze znanego podziału na -way, z tym wyjątkiem, że mamy ograniczenie liczby liczb w każdej partycji. Dla k = 2 można zaproponować następujący prosty algorytm wielomianowy,$m$$k = 2$

• Załóżmy, że numery są klasyfikowane, tj 1 < 2 < . . . < a n . Następnie przez ı ≤ m ZBYWAĆ o I do podgrupy I , na ı > m , przypisanie do podzestawu n - I + 1 .$a_1<a_2<...<a_n$$i≤m$$a_i$$i$$i>m$$n−i+1$

Nietrudno zrozumieć, dlaczego algorytm działa. Po prostu wybierz dwa dowolne pojemniki. Jakakolwiek zamiana liczb nie zwiększy ilości produktu.

Ale w przypadku większych zastanawiam się, czy problem można rozwiązać w czasie wielomianowym, czy nie? Byłbym również wdzięczny, gdyby ktoś mógł pokazać, że jest to twardość np.$k$

Uwaga: napotkałem problem podczas pracy nad problemem planowania w sieciach bezprzewodowych. Znalazłem dobry algorytm heurystyczny do rozwiązania problemu. Ale po chwili pomyślałem, że problem może być teoretycznie interesujący.

(To jest nieco bardziej szczegółowa wersja moich komentarzy do pytania.)

Jak sugeruje turkistany w komentarzu do pytania, problem ten jest trudny dla NP dla każdej stałej k ≥3 przez redukcję z problemu podziału k . Redukcja w ogóle nie zmienia instancji: pamiętaj tylko, że maksimum iloczynu sum wynosi co najmniej (∑ a _i / k ) ^m wtedy i tylko wtedy, gdy liczby można podzielić na m zestawy, każdy o rozmiarze k, którego sumy są wszyscy równi.

Zauważ, że dane wejściowe do problemu k- partycji są zwykle definiowane jako liczby km, które mogą nie być całkowicie różne , i jest to niezbędne w standardowym dowodzie kompletności NP (takim jak ten w Garey i Johnson ). Dlatego powyższe zmniejszenie świadczy jedynie o twardości NP niewielkiego uogólnienia obecnego problemu, w którym dane wejściowe mogą być wielosekcyjne zamiast zestawu. Jednak tę lukę można wypełnić, ponieważ problem z partycją k pozostaje NP-zupełny, nawet jeśli liczby na wejściu muszą być wszystkie odrębne; patrz [HWW08] dla przypadku k = 3 (patrz także odpowiedź Serge Gaspersna inne pytanie), które można łatwo modyfikować dla większych wartości k .

Ponadto wszystko tu podane pozostaje NP-zupełne / NP-twarde, nawet jeśli liczby na wejściu są podane jednostronnie.

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Multigraficzne realizacje sekwencji stopni: Maksymalizacja jest łatwa, minimalizacja jest trudna. Operacje Research Letters , 36 (5): 594-596, wrzesień 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004