Jak fundamentalne są matroidy i greedoidy w projektowaniu algorytmów?

Początkowo wprowadzono matroidy , aby uogólnić pojęcia liniowej niezależności zbioru podzbiorów stosunku do zbioru podłoża . Niektóre problemy, które zawierają tę strukturę, pozwalają chciwym algorytmom znaleźć optymalne rozwiązania. Koncepcja greedoidów została później wprowadzona w celu uogólnienia tej struktury, aby uchwycić więcej problemów, które pozwalają na znalezienie optymalnych rozwiązań za pomocą chciwych metod. $E$ $I$

Jak często te struktury powstają w projektowaniu algorytmów?

Co więcej, często chciwy algorytm nie będzie w stanie w pełni uchwycić tego, co jest konieczne do znalezienia optymalnych rozwiązań, ale nadal może znaleźć bardzo dobre przybliżone rozwiązania (na przykład pakowanie bin). Biorąc to pod uwagę, czy istnieje sposób zmierzenia, jak „blisko” jest problem z greedoidą lub matroidem?

algorithms optimization combinatorics greedy-algorithms matroids Nicholas Mancuso
źródło

Odpowiedzi:

Trudno jest odpowiedzieć na pytanie „jak często”. Ale podobnie jak w przypadku wszystkich „podstawowych struktur” korzyść wynika z faktu, że podstawowy problem, który próbuje się rozwiązać, ma strukturę matroidu (lub chciwości). To nie tylko problemy z matroidem. Problem przecięcia macierzy ma określony model (dopasowanie dwustronne).

Nick Harvey dość niedawno napisał pracę doktorską na temat algorytmów problemów z matroidem, a także przyjrzał się optymalizacji funkcji podmodularnych (która uogólnia problemy z matroidem). Pomocne może być przeczytanie wstępu i tła pracy magisterskiej.

Suresh
źródło

Chcę tylko dodać notatkę dotyczącą „bliskości”. Jeśli zachłanny algorytm podaje przybliżenie k, problem może być skonstruowany jako k-matroid.

Nicholas Mancuso,

+1. Niezła odpowiedź. Zastanawiam się, dlaczego teza mówi, że funkcja podmodularna jest uogólnieniem lub stresem matroidu? Jedyne połączenie, jakie mogę znaleźć między tymi dwoma, to ranga submatroidu w podzbiorze to funkcja submodularna.

Tim

Istnieje bardzo eleganckie połączenie geometryczne. Aby lepiej to zrozumieć, powinieneś sprawdzić en.wikipedia.org/wiki/Polymatroid . Z grubsza, jeśli polytop związany z funkcją submodularną ma określone właściwości, otrzymujesz matroid. Więcej informacji na ten temat można znaleźć w książce Satoru Fujishige: kurims.kyoto-u.ac.jp/~fujishig/Book1a.html

Suresh

Jak wskazano w CLRS (strona 437 trzeciego wydania), teoria matroidów nie obejmuje problemu wyboru aktywności i problemu kodowania Huffmana. Czy obejmuje je teoria chciwości?

hengxin