dodatki do zar04

ZADANIE 33 (3 pkt) 2/3-aproksymacja skojarzenia maximum
dla grafów dwudz (L,R) o stałym stopniu na L /podobne do Z.32/
algorytm powinien działać w stałym czasie
wskazówka: obl skoj maximal, a potem usunąć ścieżki rozszerzające długości=3
graf warstwowy o 3 warstwach, w nim pakowanie śc roz dł=3, potem "rozszerzyć" te śc roz
patrz: algorytm Hopcroft-Karp do aproks skojarzeń...

ZADANIE 34 (3 pkt) (prj+ref) (1-eps)-aproksymacja skojarzenia maximum
założenia jak w Z.33; algorytm powinien działać w czasie O(1/eps)

ZADANIE 35 (3 pkt) (ref) długość segm w alg MM
wyjaśnić dlaczego w alg MM O(log^4n) "segm zorientowane" muszą mieć dł>log^2n
natomiast w alg M. Fisher wystarczy dł>logn
należy samodzielnie zgłębić literaturę...
opis alg MM O(log^4n) /ze spannerem/ można znaleźć tutaj (rozdz 2)
alg M. Fisher: "Improved Deterministic Distributed Matching via Rounding", link

ZADANIE 36 f-skojarzenia maximal w grafie dwudzielnym
jest to prosta modyfikacja Z.32 z f-skoj zamiast skoj;
def f-skoj: podgraf M, na L d_M(v)≤1, na R d_M(v)≤f(v);
motywacja: serwer v in R, może obsługiwać f(v) klientów.