Zrównoważone partycjonowanie liczb

Zrównoważone partycjonowanie liczb to wariant wielowymiarowego partycjonowania liczb , w którym istnieją ograniczenia dotyczące liczby elementów przydzielonych do każdego zestawu. Dane wejściowe do problemu to zbiór n elementów o różnych rozmiarach i dwie liczby całkowite m , k . Wynikiem jest podział elementów na m podzbiorów, tak że liczba elementów w każdym podzbiorze wynosi co najwyżej k . Z zastrzeżeniem tego wymagane jest, aby sumy rozmiarów w m podzbiorach były jak najbardziej podobne.

Przykładem aplikacji jest planowanie identycznych maszyn , gdzie każda maszyna ma kolejkę zadań, która może pomieścić co najwyżej k zadań. Problem ma zastosowanie również w produkcji VLSI oraz przy przypisywaniu narzędzi do maszyn w elastycznych systemach produkcyjnych .

W standardowej trójpolowej notacji dla problemów z optymalnym planowaniem zadań problem minimalizacji największej sumy jest czasami oznaczany jako „ P | # ≤ k | C _max ”. Środkowe pole „ # ≤ k ” oznacza, że liczba zadań w każdej maszynie powinna wynosić co najwyżej k . Kontrastuje to z wersją nieograniczoną, która jest oznaczona przez „ ${\ Displaystyle P \ równoległy C _ {\ max}}$ ".

Dwukierunkowe zrównoważone partycjonowanie

Typowy przypadek specjalny zwany dwukierunkowym zrównoważonym partycjonowaniem ma miejsce, gdy powinny istnieć dwa podzbiory ( m = 2). Dwa podzbiory powinny zawierać elementy podłogi ( n /2) i sufitu ( n /2). Jest to wariant problemu partycji . Rozstrzygnięcie, czy istnieje podział, w którym sumy w dwóch podzbiorach są równe, jest NP-trudne; patrz problem [SP12]. Istnieje wiele algorytmów, których celem jest znalezienie zrównoważonego podziału, w którym suma jest jak najbardziej równa.

Coffman, Frederickson i Lueker przedstawiają ograniczoną wersję algorytmu LPT (tzw. RLPT), w której wejścia są przypisywane parami. Gdy dane wejściowe są zmiennymi losowymi o rozkładzie równomiernym, oczekiwana największa suma RLPT wynosi dokładnie ${\ Displaystyle {\ Frac {n} {4}} + {\ Frac {1} {2n + 2} }}$ . Oczekiwana różnica w pracy (różnica między największą a najmniejszą sumą) wynosi ${\ Displaystyle \ Theta (1/n)}$ .
Lueker przedstawia wariant algorytmu LDM (nazywany metodą różnicowania parami (PDM)). Jego oczekiwana różnica w pracy wynosi ${\ Displaystyle \ Theta (1/n)}$ .
Tsai przedstawia algorytm o nazwie Ograniczona największa różnica (RLD). Jego różnica w pracy jest prawie na pewno ${\ Displaystyle O (\ log n/n ^ {2})}$
Yakir przedstawia zrównoważony wariant algorytmu LDM dla m = 2, nazwany BLDM. Jego oczekiwana różnica w pracy wynosi ${\ Displaystyle n ^ {- \ Theta (\ log n)}}$ .
Mertens przedstawia kompletny algorytm w każdej chwili dla zrównoważonego partycjonowania dwukierunkowego. Łączy algorytm BLDM z algorytmem pełnego Karmarkara-Karpa.

Zrównoważone partycjonowanie trójek

Innym szczególnym przypadkiem zwanym podziałem na 3 partycje jest sytuacja, w której liczba elementów w każdym podzbiorze powinna wynosić co najwyżej 3 ( k = 3). Decydowanie, czy istnieje taki podział z równymi sumami, jest dokładnie problemem 3-podziału , o którym wiadomo, że jest silnie NP-trudny . Istnieją algorytmy aproksymacji, które mają na celu znalezienie podziału, w którym suma jest jak najbardziej równa.

Kellerer i Woeginger dostosowują algorytm LPT do partycjonowania trypletowego (gdzie jest co najwyżej 3* m pozycji, a każdy podzbiór powinien zawierać co najwyżej 3 pozycje). Ich algorytm nazywa się „zmodyfikowany-LPT” lub „MLPT” . Sortuje elementy od dużych do małych i umieszcza każdy element po kolei w koszu z najmniejszą sumą spośród tych pojemników, które zawierają mniej niż 3 elementy. Pokazują, że algorytm MLPT osiąga co najwyżej $nieograniczonego$ jest tym samym współczynnikiem przybliżenia, jaki osiąga dla problemu . Granica jest napięta dla MLPT.
Chen, He i Lin pokazują, że dla tego samego problemu MLPT osiąga co najmniej ${\ Displaystyle {\ Frac {3m-1} {4m-2}}}$ maksymalnej najmniejszej sumy, która jest ponownie tym samym stosunkiem, który osiąga LPT dla problemu nieograniczonego.
$.$ przedstawiają inny algorytm (dla przypadku dokładnie 3 * m elementów), który osiąga najwyżej minimalną największą sumę

Zrównoważone partycjonowanie z większą licznością

Bardziej ogólny przypadek, zwany k -partycjonowaniem , występuje wtedy, gdy liczba elementów w każdym podzbiorze powinna wynosić co najwyżej k , gdzie k może być dowolną dodatnią liczbą całkowitą.

Babel, Kellerer i Kotov badają wariant, w którym występuje k × m elementów (dla pewnej liczby całkowitej k ), a każdy z m zbiorów musi zawierać dokładnie k elementów. Przedstawiają kilka heurystycznych algorytmów aproksymacji minimalnej największej sumy:
- Algorytm składania : optymalny dla m = 2 i ogólnie ma ścisły współczynnik przybliżenia ${\ Displaystyle 2- {\ Frac {1} {m}}}$ .
- Algorytm wymiany : ścisły współczynnik przybliżenia ${\ Displaystyle 2- {\ Frac {2} {m + 1}}}$ . Nie wiadomo, czy działa w czasie wielomianowym.
- Algorytm pierwotny-dual (połączenie LPT i MultiFit ): współczynnik aproksymacji co najwyżej ${\ Displaystyle 4/3}$ . Jest ciasny dla k = 4, gdy m jest wystarczająco duże; dokładna dolna granica to ${\ Displaystyle {\ Frac {4m} {3m + 1}}}$ .
- Przypuszczenie również, że Modified-LPT ma współczynnik aproksymacji ${\ Displaystyle {\ Frac {4m-1} {3m}}}$ . Obecnie wiadomo, że to przypuszczenie jest prawdziwe tylko dla k = 3. Dla k > 3 wiadomo, że jego współczynnik aproksymacji wynosi co najwyżej 2.
Michiels, Korst, Aarts, van Leeuwen i Spieksma badają wariant, w którym każdy z zestawów m musi zawierać pozycje sufitowe ( n / m ) lub elementy podłogowe ( n / m ) (więc k = sufit ( n / m )). Rozszerzają Balanced-LDM (BLDM) od m = 2 do ogólnego m . Uogólniony algorytm działa w czasie ${\ Displaystyle O (n \ log n)}$ . Dowodzą, że jego współczynnik aproksymacji dla minimalnej największej sumy wynosi dokładnie 4/3 dla k = 3, 19/12 dla k = 4, 103/60 dla k = 5, 643/360 dla k = 6 i 4603/2520 dla k = 7. Stosunki obliczono, rozwiązując program liniowy z liczbami całkowitymi mieszanymi . Ogólnie (dla dowolnego k ) współczynnik aproksymacji wynosi co najmniej ${\ Displaystyle 2- \ suma _ {j = 0} ^ {k-1} {\ Frac {j!} {k!}}} i co najwyżej$ 2 $\ Displaystyle 2 - {\ Frac { 1}{k-1}}}$ . Dokładne wyniki MILP dla 3,4,5,6,7 odpowiadają dolnej granicy. Dla k > 7 nie są znane dokładne wyniki, ale różnica między dolną a górną granicą jest mniejsza niż 0,3%. Gdy parametrem jest liczba podzbiorów ( m ), współczynnik aproksymacji wynosi dokładnie ${\ displaystyle 2- {\ frac {1} {m}}}$ .
Zhang, Mouratidis i Pang pokazują, że BLDM może dawać partycje o dużej różnicy pracy (różnica między najwyższą a najniższą sumą), zarówno gdy dane wejściowe są rozłożone równomiernie, jak i gdy ich rozkład jest skośny. Proponują dwie alternatywne heurystyki: LRM zmniejsza różnicę pracy do 1/3 różnicy pracy BLDM, gdy rozkład jest jednolity; Meld zmniejsza różnicę w pracy, gdy dystrybucja jest przekrzywiona. Algorytm hybrydowy łączy BLDM, LRM i Meld i dynamicznie dostosowuje się do różnych dystrybucji danych.
Kiedy k jest ustalone, PTAS Hochbauma i Shmoysa może być użyty do zrównoważonego podziału. Gdy k jest częścią danych wejściowych, obecnie nie jest znany żaden PTAS.
Dell'Amico i Martello badają problem minimalizacji największej sumy, gdy liczba elementów we wszystkich zestawach wynosi co najwyżej k . Pokazują one, że relaksacja programu liniowego tego wariantu ma taką samą optymalną wartość jak relaksacja LP wariantu nieograniczonego. Wyrażenie ${\ Displaystyle \ max ((\ suma x_ {i}) / m, x_ {1})}$ , gdzie x _i to dane wejściowe uporządkowane od dużych do małych , jest dolną granicą optymalnej największej sumy, a jej stosunek najgorszego przypadku wynosi 1/2 w obu wariantach. ulepszone wyrażenie ${\ Displaystyle \ max ((\ suma x_ {i}) / m, x_ {1}, x_ {k} +x_{m+1})}$ ma współczynnik najgorszego przypadku 2/3 w wariancie nieograniczonym i 1/2 w wariancie z ograniczeniami. Współczynnik aproksymacji zmodyfikowanego szeregowania listy wynosi 1/2 dla wariantu nieograniczonego, ale wynosi 0 dla wariantu ograniczonego (może być dowolnie zły). Współczynnik aproksymacji zmodyfikowanego algorytmu LPT wynosi co najwyżej 2. Pokazują również, że dolna granica algorytmu ma wąski współczynnik wydajności w najgorszym przypadku wynoszący 3/4, a ich algorytm PD ma wąski współczynnik wydajności wynoszący 4/3 (kiedy m jest wystarczająco duży).
On, Tan, Zhu i Yao rozważają problem maksymalizacji najmniejszej sumy. Pokazują $algorytm$ . Przedstawiają nowy algorytm, HARMONIC1, ze współczynnikiem najgorszego przypadku co najmniej ${\ Displaystyle \ max \ lewo ({\ Frac {1} {k} },{\frac {1}{\lceil \sum _{i=1}^{m}{\frac {1}{i}}\rceil +1}}\right)}$ . Oba te algorytmy są porządkowe — dzielą pozycje na podstawie kolejności między nimi, a nie ich dokładnych wartości. Dowodzą, że $najwyżej$ algorytm do najmniejszej Oznacza to, że HARMONIC1 jest asymptotycznie optymalny. Dla dowolnego ustalonego k każdy algorytm porządkowy ma stosunek co najwyżej najmniejszego pierwiastka równania ${\ Displaystyle \ suma _ {i = 1} ^ {m }\left\lfloor \left\lfloor {\frac {k+i-1}{i}}\right\rfloor x\right\rfloor =k}$ . Kiedy k dąży do nieskończoności, ta górna granica zbliża się do 0.

Relacje między problemami zrównoważonymi i nieograniczonymi

Istnieją pewne ogólne zależności między przybliżeniami problemu zrównoważonego podziału a standardowym (nieograniczonym) problemem podziału.

$,$ że stosunek między optimum nieograniczonym a optimum ograniczonym wynosi co najwyżej .
Kellerer i Kotov dowodzą, że każda heurystyka dla zrównoważonego podziału z pojemnością k i współczynnikiem aproksymacji r (dla minimalnej największej sumy) może być wykorzystana do uzyskania heurystyki dla nieograniczonego podziału ze współczynnikiem aproksymacji ${\ Displaystyle \ max \ lewo (r, {\ Frac {k + 2} {k + 1}} - {\ Frac {1} {m (k + 1)}} \ prawo )}$ . W szczególności ich algorytm aproksymacji dla partycjonowania trypletów ( $k$ ${\ Displaystyle \ max \ lewo ({\ Frac {7} {6}}, {\ Frac {5} {4}} - {\ Frac {1} {4m}} \ prawej)}$ być użyty do uzyskania heurystyki dla partycjonowania nieograniczonego ze współczynnikiem aproksymacji - .

Różne ograniczenia liczności

Ograniczenia liczności można uogólnić, dopuszczając różne ograniczenia dla każdego podzbioru. Wariant ten został wprowadzony w sekcji „otwarte problemy” dokumentu, który nazywa problem ki _{- partycjonowania} . On, Tan, Zhu i Yao przedstawiają algorytm o nazwie HARMONIC2 służący do maksymalizacji najmniejszej sumy z różnymi ograniczeniami liczności. Dowodzą, że jego współczynnik najgorszego przypadku wynosi co najmniej ${\ Displaystyle \ max \ lewo ({\ Frac {1} {k_ {m}}},{\frac {k_{1}}{k_{m}}}{\frac {1}{\left\lceil \sum _{i=1}^{m}{\frac {1 }{i}}\right\rceil +1}}\right)}$ .

Skategoryzowane ograniczenia liczności

Inne uogólnienie ograniczeń liczności jest następujące. Elementy wejściowe są podzielone na k kategorii. Dla każdej kategorii h istnieje ograniczenie wydajności k _h . Każdy z m podzbiorów może zawierać co najwyżej k _h pozycji z kategorii h . Innymi słowy: wszystkie m podzbiory powinny być niezależnymi zbiorami danej macierzy partycji . Zbadano dwa szczególne przypadki tego problemu.

Partycjonowanie jądra

W problemie zrównoważonego partycjonowania jądra niektóre m predefiniowanych elementów to jądra , a każdy z m podzbiorów musi zawierać pojedyncze jądro (i nieograniczoną liczbę elementów innych niż jądro). Tutaj są dwie kategorie: kategoria jądra o pojemności 1 i kategoria niezwiązana z jądrem o nieograniczonej pojemności.

Chen, He i Yao dowodzą, że problem jest NP-trudny nawet dla k = 3 (dla k = 2 można go skutecznie rozwiązać, znajdując maksymalne dopasowanie wagowe ). Następnie przedstawiają algorytm zwany Kernel-LPT (KLPT): przypisuje jądro do każdego podzbioru, a następnie uruchamia zmodyfikowany algorytm LPT (umieszcza każdy element w podzbiorze o najmniejszej sumie spośród tych, które mają mniej niż k elementów). Dowodzą, że przy $.$ = 3 dla minimalnej największej Jednak Chen, He i Lin twierdzą, że jego ścisły współczynnik przybliżenia wynosi ${\ Displaystyle {\ Frac {3m-1} {2m}}}$ dla minimalnej największej sumy ^{[ potrzebne wyjaśnienie ]} i ${\ Displaystyle {\ Frac {2m-1}, {3m-2}}}$ dla maksymalnej najmniejszej sumy.

Jedno partycjonowanie na kategorię

W innym wariancie tego problemu istnieje kilka k kategorii o rozmiarze m , a każdy podzbiór powinien zawierać dokładnie jeden element z każdej kategorii. Oznacza to, że k _h = 1 dla każdej kategorii h .

Wu i Yao przedstawili warstwowy algorytm LPT – wariant algorytmu LPT . Dowodzą, że jego współczynnik aproksymacji $wynosi$ sumy ${\ Displaystyle {\ Frac {1} {m}}}$ do maksymalizacji najmniejszej sumy w ogólnym przypadku; aw niektórych szczególnych przypadkach można go poprawić do ogólnego $m$ i $-1}{2m-3}}}$ $Displaystyle {\$ } dla k = 3.
Li i Li przedstawili różne algorytmy dla tego samego problemu. Aby zminimalizować największą sumę, przedstawiają EPTAS dla stałej k i FPTAS dla stałej m . Aby zmaksymalizować najmniejszą sumę, przedstawiają algorytm aproksymacji 1/( k - 1) dla przypadku ogólnego i EPTAS dla stałej k . Badają również bardziej ogólny cel: minimalizację lp-normy wektora sum. Dowodzą, że algorytm Layered-LPT jest algorytmem 2-przybliżenia dla wszystkich norm.
Dell'Olmo, Hansen, Pallottino i Storchi badają 32 różne cele tego problemu. Dla każdego z czterech operatorów max, min, sum, diff jeden operator można zastosować do k elementów w każdym podzbiorze, a następnie jeden operator można zastosować do m wyników dla różnych podzbiorów. Każdy z tych 16 celów można zmaksymalizować lub zminimalizować, w sumie 32. Pokazują one, że 21 z tych problemów można rozwiązać w czasie liniowym; 7 wymagają bardziej złożonych, ale wciąż wielomianowych algorytmów; 3 są NP-trudne: maksymalizacja (min, suma), minimalizacja (max, suma) i minimalizacja (diff, suma). Zostawili otwarty stan minimalizowania (diff, diff).

Zobacz też

Partycjonowanie liczb z ograniczeniami matroidów jest uogólnieniem, w którym jako parametr podawana jest stała matroida, a każdy z m podzbiorów powinien być niezależnym zbiorem lub podstawą tej matroidy.

Ograniczenia liczności to szczególne przypadki ograniczeń matroidów, w których matroid jest jednolitym matroidem .
Skategoryzowane ograniczenia liczności to szczególny przypadek, w którym matroid jest matroidem partycji .