MIT
50
Exact Algorithm
lRandomly
partition edges in two groups
»each
like a ½ -sample: e = O*(c-½)
lRecursively
pack trees in each half
»c/2 - O*(c½)
trees
lMerge
packings
»gives
packing of size c - O*(c½)
»augment
to maximum packing: O*(mc½)
lT(m,c)=2T(m/2,c/2)+O*(mc½) = O*(mc½)