Partycjonowanie liczb ograniczone przez matroidy

Partycjonowanie liczb z ograniczeniami matroidów jest wariantem problemu wielokierunkowego partycjonowania liczb , w którym podzbiory w podziale powinny być niezależnymi zbiorami matroida . Dane wejściowe do tego problemu to zbiór S elementów, dodatnia liczba całkowita m i kilka m matroidów w tym samym zbiorze S . Celem jest podzielenie S na m podzbiorów, tak aby każdy podzbiór i był niezależnym zbiorem w matroidzie i . Z zastrzeżeniem tego ograniczenia, niektóre funkcje celu powinny zostać zminimalizowane, na przykład, minimalizując rozmiary elementów o największej sumie w podzbiorze. W bardziej ogólnym wariancie każda z m matroidów ma funkcję wagi, która przypisuje wagę każdemu elementowi zestawu naziemnego. Rozważano różne funkcje celu. Dla każdego z trzech operatorów max, min, sum można użyć tego operatora na wagach elementów w każdym podzbiorze i na samych podzbiorach. W sumie istnieje 9 możliwych funkcji celu, z których każdą można zmaksymalizować lub zminimalizować.

Przypadki specjalne

Niektóre ważne szczególne przypadki problemów z partycjonowaniem ograniczonym przez matroidy to:

• Cel (maks., suma) to maksimum we wszystkich podzbiorach całkowitej wagi w podzbiorze. Kiedy pozycje reprezentują zadania, a wagi reprezentują ich długość, cel ten jest po prostu rozpiętością harmonogramu . Dlatego minimalizacja tego celu jest równoznaczna z minimalizacją makepan pod ograniczeniami matroidów. Podwójny cel maksymalizacji (min, suma) był również badany w tym kontekście.
  • Szczególny przypadek, w którym matroidy są wolnymi matroidami (bez ograniczeń), a m funkcji wagowych są identyczne, odpowiada szeregowaniu identycznych maszyn , znanemu również jako wielokierunkowe partycjonowanie liczb . Przypadek wolnych matroidów i różnych funkcji wagi odpowiada szeregowaniu niepowiązanych maszyn .
  • Szczególny przypadek jednolitych matroidów odpowiada ograniczeniom liczności w podzbiorach. Bardziej ogólny przypadek matroidów partycji odpowiada skategoryzowanym ograniczeniom liczności. Problemy te są opisane na stronie poświęconej partycjonowaniu liczb zrównoważonych .
• Cel (suma, suma) jest sumą wag wszystkich pozycji we wszystkich podzbiorach, gdzie wagi w każdym podzbiorze i są obliczane na podstawie funkcji wagi matroidu i . Minimalizowanie tego celu można sprowadzić do problemu ważonego przecięcia matroidów - znalezienia podzbioru o maksymalnej masie, który jest jednocześnie niezależny w dwóch danych matroidach. Ten problem można rozwiązać w czasie wielomianowym.
• Celem (max, max) jest maksymalna waga we wszystkich podzbiorach, gdzie wagi w każdym podzbiorze i są obliczane na podstawie funkcji wagi matroidu i . Minimalizacja tego celu za pomocą matroidów graficznych może być wykorzystana do rozwiązania problemu drzewa rozpinającego z minimalnym wąskim gardłem .
• Cel (suma, min) jest sumą minimalnych wag we wszystkich podzbiorach. Maksymalizacja tego celu za pomocą k identycznych graficznych matroidów może być wykorzystana do rozwiązania problemu podziału drzewa o maksymalnej całkowitej pojemności .
• Cel (sum,max) jest sumą maksymalnych wag we wszystkich podzbiorach. Ten cel może reprezentować całkowitą pamięć potrzebną do planowania, , gdy każdy matroid i reprezentuje możliwe alokacje w maszynie i .

Ogólne ograniczenia matroidów

Ogólne ograniczenia matroidowe zostały po raz pierwszy rozważone przez Burkarda i Yao. Pokazali, że minimalizację (sum,max) można przeprowadzić w czasie wielomianowym za pomocą zachłannego algorytmu dla podklasy matroidów, która obejmuje matroidy partycji . Hwang i Rothblum przedstawili alternatywny warunek wystarczający.

Wu i Yao przedstawili algorytm aproksymacji do minimalizacji (max, suma) z ogólnymi ograniczeniami matroidów.

Abbassi, Mirrokni i Thakur przedstawiają algorytm aproksymacyjny dla problemu maksymalizacji różnorodności przy ograniczeniach matroidowych.

Kawase, Kimura, Makino i Sumita pokazują, że problemy maksymalizacji można sprowadzić do problemów minimalizacji. Następnie analizują siedem problemów minimalizacji:

• Minimalizowanie (suma, maks): problem jest silnie NP-trudny, nawet gdy matroidy i wagi są identyczne. Istnieje PTAS dla identycznych matroidów i ciężarków. Dla ogólnych matroidów i wag istnieje εm dla dowolnego ε > 0. Jest on NP-trudny do aproksymacji współczynnikiem O(log m ).
• Minimalizowanie (min, min), (max, max), (min, max) i (min, suma): istnieją algorytmy czasu wielomianowego. Redukują problemy do problemu wykonalności partycjonowania matroidów .
• Minimalizowanie (max, min) i (suma, min): istnieją algorytmy czasu wielomianowego dla identycznych matroidów i wag. W ogólnym przypadku jest to silnie NP-trudne nawet do przybliżenia.
• Pozostałe dwa problemy były analizowane w poprzednich pracach: minimalizacja (max,suma) jest silnie NP-trudna ( specjalnym przypadkiem jest 3-partycja ), a minimalizacja (suma,suma) może być zredukowana do ważonego przecięcia matroidów , które jest wielomianem.

Powiązane problemy

Partycjonowanie matroidów to inny problem, w którym liczba części m nie jest ustalona. Istnieje pojedyncza matroid, a celem jest podzielenie jej elementów na jak najmniejszą liczbę niezależnych zestawów.