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