Tight RNC Approximations to Max Flow
Lists
Only you see this
Abstract
We show here that the general Maximum Flow problem can be approximated by a RNC algorithm in such a way that for any fixed (or at most polynomially bounded) ε, the absolute performance ratio is at most 1+1/ε. Our results furthermore imply that there is a fully NC approximation scheme for the Maximum Flow problem if and only if there is an algorithm in NC to construct a Maximum Matching in a bipartite graph.
BibTeX
@inproceedings{serna1991tight,
author = {Maria J. Serna and Paul G. Spirakis},
title = {{Tight RNC Approximations to Max Flow}},
booktitle = {STACS},
year = {1991},
url = {https://openreview.net/forum?id=oidcqMg3AI},
}Loading related content...