MIT
49
Las Vegas Algorithm
lPacking
algorithm is Monte Carlo
lPreviously
found approximate cut (faster)
lIf
close, each “certifies” other
»Cut
exceeds optimum cut
»Packing
below optimum cut
lIf
not, re-run both
lResult: Las Vegas, expected
time O*(rm)