Twardość NP specjalnego przypadku podziału na liczby

Rozważ następujący problem,

Biorąc pod uwagę zestaw dodatnimi liczbami , w którym jest stała, chcemy podzielić wkomponowany podzbiorów wielkości , 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 można zaproponować następujący prosty algorytm wielomianowy, $m$ $k = 2$

Załóżmy, że numery są klasyfikowane, tj . Następnie przez ZBYWAĆ do podgrupy , na , przypisanie do podzestawu . $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.

— Hel
źródło

k = 2

$k=2$

@Mohsen, dzięki. Sugerowałbym, aby w pytaniu uwzględnić te komentarze dotyczące motywacji, pochodzenia i tego, co wiesz o k = 2. To prawdopodobnie uczyniłoby to bardziej interesującym dla innych.

— Kaveh,

Moją intuicją jest to, że iloczyn sumy każdego podzbioru jest maksymalizowany, gdy sumy są równe lub maksymalna różnica par jest minimalna. Przy takim założeniu uzyskujemy łatwą redukcję z 3-partycji, która jest NP-kompletna (dla k = 3).

— Mohammad Al-Turkistany

(Usunąłem dwa komentarze, które zamieściłem kilka godzin temu, aby napisać je dokładniej.) Jak sugeruje turkistany, problem z partycją k można zredukować do tego problemu, a zatem ten problem jest trudny dla NP dla każdej stałej k≥3. Jedyną istotną właściwością jest to, ż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ą równe. Produkt nie zawsze jest maksymalizowany przez partycję, która minimalizuje maksymalną różnicę par, ale nie ma to znaczenia, o ile rozważymy dokładny problem. (więcej)

— Tsuyoshi Ito

(ciąg dalszy) Jeśli wymagają wprowadzenia się zestaw zamiast MultiSet , redukcja ta nadal działa, ponieważ problem k-partycja pozostaje NP-zupełny, nawet z zestawem, ale należy zachować ostrożność, ponieważ średnia dowód NP-zupełności problemu z 3 partycjami działa tylko wtedy, gdy dane wejściowe mogą zawierać tę samą liczbę całkowitą więcej niż jeden raz. Zobacz Złożoność obliczeniowa problemu z 3 partycjami z wyraźnymi liczbami (uwaga: autopromocja).

— Tsuyoshi Ito,

(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

— Tsuyoshi Ito
źródło