Czy programowanie dynamiczne nigdy nie jest słabsze niż chciwy?

W złożoności obwodu mamy rozdzielenia mocy różnych modeli obwodów.

W złożoności dowodu mamy rozróżnienia między mocami różnych systemów dowodu.

Ale w algorytmie wciąż mamy tylko kilka różnic między potęgami paradygmatów algorytmicznych .

Moje pytania poniżej mają na celu dotknięcie tego ostatniego problemu w dwóch paradygmatach: Chciwy i Programowanie dynamiczne.

Mamy naziemny zestaw elementów, a niektóre rodziny jego podzbiorów zadeklarowano jako możliwe rozwiązania. Zakładamy, że ta rodzina jest zamknięta w dół: możliwe są podzestawy wykonalnych rozwiązań. Biorąc pod uwagę przypisanie nieujemnych wag elementom podłoża, problemem jest obliczenie maksymalnej masy całkowitej wykonalnego rozwiązania.

Algorytm zachłanny zaczyna się od pustego rozwiązania częściowego i na każdym kroku dodaje jeszcze nietraktowany element o największej masie, jeśli jest to możliwe, tj. Jeśli przedłużone rozwiązanie jest nadal wykonalne. Dobrze znane twierdzenie Rado-Edmondsa stwierdza, że ​​algorytm ten znajdzie optymalne rozwiązanie dla wszystkich wag wejściowych, jeśli rodzina możliwych rozwiązań jest matroidem.

Z grubsza mówiąc, algorytm DP jest prosty , jeśli wykorzystuje tylko operacje Max i Sum (lub Min i Sum). Mówiąc dokładniej (jak sugeruje Joshua), przez prosty algorytm DP rozumiem obwód (max, +) z bramkami Fanin-2 Max i Sum. Dane wejściowe są zmiennymi, których -ta odpowiada masie nadanej -temu elementowi. Taki obwód może rozwiązać każdy taki problem, po prostu obliczając maksymalną całkowitą masę wykonalnego rozwiązania. Ale może to być ogromny przesada, jeśli mamy wykładniczo wiele takich rozwiązań (jak prawie zawsze tak jest).$i$$i$

Pytanie 1: Czy istnieją matroidy, na których jakikolwiek prosty algorytm DP będzie wymagał super wielomianowej liczby operacji, aby rozwiązać odpowiedni problem maksymalizacji?

KOMENTARZ (dodane 24.12.2015): To pytanie jest już odpowiedź (patrz poniżej): tam są takie matroids, nawet w przytłaczającej większości.

Następne pytanie dotyczy oddzielenia Chciwego i prostego DP w przypadku problemów z przybliżeniem . W przypadku problemu maksymalnego dopasowania rodzina wykonalnych rozwiązań obejmuje wszystkie dopasowania na pełnym dwudzielnym wykresie . Dla danego przypisania ciężarów do jego krawędzi, celem jest obliczenie maksymalnej wagi dopasowania (zawsze będzie to idealne dopasowanie, ponieważ waga jest nieujemna). $n\times n$

Prosty, zachłanny algorytm może przybliżyć ten problem do współczynnika 2: po prostu zawsze bierz niewidoczną, rozłączną krawędź maksymalnej masy. Otrzymana waga będzie wynosić co najmniej połowę masy optymalnej.

Pytanie 2: Czy prosty algorytm DP może w przybliżeniu rozwiązać problem dopasowania do masy w ramach współczynnika 2, wykorzystując tylko wielomianowo wiele operacji Max i Sum?

Oczywiście trywialny algorytm DP, który wyprowadza krotność maksymalnej masy krawędzi, przybliża ten problem do współczynnika n . Ale chcemy znacznie mniejszego czynnika. Myślę, że nie da się osiągnąć nawet współczynnika n / log n , ale znowu: jak to udowodnić ? $n$$n$$n/\log n$

POWIĄZANE: Kuzynem dopasowania maksymalnej wagi jest problem z przypisaniem : znajdź minimalną wagę idealnego dopasowania. Problem ten można rozwiązać (nawet dokładnie) przez programowanie liniowe (tzw. Algorytm węgierski) przy użyciu tylko operacji . Ale dolna granica Razborowa dotycząca wielkości monotonicznych obwodów boolowskich obliczających funkcję stałą oznacza (niezupełnie bezpośrednio), że każdy obwód (min, +) przybliżający ten problem w dowolnym (!) Skończonym współczynniku musi wykorzystywać operacje n Ω ( log n ) . Zatem w celu minimalizacji$O(n^3)$$n^{\Omega(\log n)}$problemy, proste algorytmy DP mogą być znacznie słabsze niż programowanie liniowe. Moje powyższe pytania mają na celu wykazanie, że takie algorytmy DP mogą być nawet słabsze niż Chciwi.

Czy ktoś widział, że ktoś rozważa podobne pytania?

---

DODATKOWO (24.12.2015): Pytanie 2 ma na celu wykazanie, że jeden konkretny problem maksymalizacji (problem dopasowania maksymalnego), który może być aproksymowany przez chciwy algorytm o współczynniku $r=2$ , nie może być aproksymowany prostym wielowymiarowym DP z tym samym współczynnikiem . W międzyczasie uzyskałem słabszą separację między Chciwym a prostym DP: dla każdego istnieje wyraźny problem maksymalizacji, który może być aproksymowany przez algorytm zachłanny przy współczynniku , ale nie ma prostego wielowymiarowego Algorytm DP może przybliżyć ten problem mniejszym współczynnikiem (patrz tutajr = o ( n / log n ) $r$$r=o(n/\log n)$$r$$< r/3$na szkic). Jednak samo pytanie 2 (niekoniecznie w przypadku tego konkretnego problemu z maksymalną wagą) pozostaje aktualne: interesujące byłoby skierowanie tego samego czynnika na oba algorytmy.

Myślę, że odpowiedź na moje pytanie 1 jest twierdząca : tam są matroids na której prosta DP nie źle! Oznacza to, że prosty DP może być znacznie gorszy niż Chciwy, gdy próbuje dokładnie rozwiązać problem optymalizacji .

Niech zestaw podłoża składa się ze wszystkich krawędzi . Jako nasza rodzina wykonalnych rozwiązań weźmy rodzinę wszystkich lasów w . To motroid, a jego podstawy obejmują drzewa. Tak więc odpowiadający temu wielomianowi matroidowemu jest wielomianowy wielomian którego monomale odpowiadają drzewom opinającym. Jerrum i Snir udowodnili (w rozdziale 4.5), że wymaga monotonicznych obwodów arytmetycznych o wielkości wykładniczej. To już implikuje, że każdy obwód , a więc także każdy prosty algorytm DP, musi użyć wykładniczej liczby operacji Max i Sum, aby rozwiązać problem drzewa rozpinającego maksymalną wagę. $K_n$$K_n$$f$$f$$(\max,+)$

Jako Igor Siergiejew powiedział mi, twierdząca odpowiedź na pytanie 1 następuje także poprzez zliczanie: Knuth wykazały, że istnieją matroids na punktów. $2^{2^n/n^{3/2}}$$n$

PS Nie „zaakceptuję” tej mojej pół-odpowiedzi (która pojawiła się dopiero teraz, po przemyśleniu połączenia z monotonicznymi obwodami arytmetycznymi), ponieważ pozostaje o wiele bardziej interesujące pytanie 2: o ile gorsze może być proste DP niż Chciwy przy przybliżaniu optymalizacji problemy? To pytanie jest bardziej interesujące, ponieważ Chciwy często ma dość dobry współczynnik przybliżenia. Współczynnik ten jest znany (!) Z tak zwanym „ilorazem rangi” podstawowej rodziny wykonalnych rozwiązań (patrz np. Niniejszy opis . W przypadku problemu dopasowania maksymalnej wagi, iloraz ten wynosi i wynosi najwięcej dla dowolnego przecięcia$2$$k$$k$matroidy. Z drugiej strony, o ile mi wiadomo, algorytmy aproksymacyjne oparte na DP zwykle używają pewnego rodzaju „skalowania” wag wejściowych i odnoszą się tylko do problemów typu „plecakowego” lub niektórych problemów z planowaniem. Negatywna odpowiedź na pytanie 2 potwierdziłaby tę pozorną „słabość zbliżenia” DP.