MIT
98
Approximation Algorithms
lComputing FAIL(p) is #P complete
[V]
lExact algorithm
seems unlikely
lApproximation
scheme
»Given
G,
p, e, outputs e-approximation
»May
be randomized:
–succeed with high
probability
»Fully
polynomial (FPRAS) if
runtime is polynomial in n, 1/e