| Las Vegas Algorithm |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Packing algorithm
is Monte Carlo |
||||||||||
| l | Previously found
approximate cut (faster) |
||||||||||
| l | If close, each
“certifies” other |
||||||||||
| » | Cut exceeds
optimum cut |
||||||||||
| » | Packing below
optimum cut |
||||||||||
| l | If not, re-run
both |
||||||||||
| l | Result:
Las Vegas, expected time O*(r2m) |
||||||||||