Tight RNC Approximations to Max Flow

Maria J. Serna, Paul G. SpirakisSTACS 1991 · OpenReview

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...

Figure