Fast Augmenting Paths by Random Sampling from Residual Graphs
Consider an n-vertex, m-edge, undirected graph with integral capacities and max-flow value v. We give a new [~ over O](m + nv)-time maximum flow algorithm. After assigning certain special sampling probabilities to edges in [~ over O](m)$ time, our algorithm is very simple: repeatedly find an augment...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2015
|
| Online Access: | http://hdl.handle.net/1721.1/97225 https://orcid.org/0000-0002-0024-5847 |
| _version_ | 1826210911834079232 |
|---|---|
| author | Karger, David R. Levine, Matthew S. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Karger, David R. Levine, Matthew S. |
| author_sort | Karger, David R. |
| collection | MIT |
| description | Consider an n-vertex, m-edge, undirected graph with integral capacities and max-flow value v. We give a new [~ over O](m + nv)-time maximum flow algorithm. After assigning certain special sampling probabilities to edges in [~ over O](m)$ time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph. Breaking from past work, we demonstrate that we can benefit by random sampling from directed (residual) graphs. We also slightly improve an algorithm for approximating flows of arbitrary value, finding a flow of value (1 - ε) times the maximum in [~ over O](m√n/ε) time. |
| first_indexed | 2024-09-23T14:57:25Z |
| format | Article |
| id | mit-1721.1/97225 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:57:25Z |
| publishDate | 2015 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/972252022-10-01T23:34:11Z Fast Augmenting Paths by Random Sampling from Residual Graphs Karger, David R. Levine, Matthew S. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Karger, David R. Consider an n-vertex, m-edge, undirected graph with integral capacities and max-flow value v. We give a new [~ over O](m + nv)-time maximum flow algorithm. After assigning certain special sampling probabilities to edges in [~ over O](m)$ time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph. Breaking from past work, we demonstrate that we can benefit by random sampling from directed (residual) graphs. We also slightly improve an algorithm for approximating flows of arbitrary value, finding a flow of value (1 - ε) times the maximum in [~ over O](m√n/ε) time. National Science Foundation (U.S.) 2015-06-08T18:40:00Z 2015-06-08T18:40:00Z 2015-03 2013-12 Article http://purl.org/eprint/type/JournalArticle 0097-5397 1095-7111 http://hdl.handle.net/1721.1/97225 Karger, David R., and Matthew S. Levine. “Fast Augmenting Paths by Random Sampling from Residual Graphs.” SIAM Journal on Computing 44, no. 2 (January 2015): 320–339. https://orcid.org/0000-0002-0024-5847 en_US http://dx.doi.org/10.1137/070705994 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics |
| spellingShingle | Karger, David R. Levine, Matthew S. Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title | Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title_full | Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title_fullStr | Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title_full_unstemmed | Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title_short | Fast Augmenting Paths by Random Sampling from Residual Graphs |
| title_sort | fast augmenting paths by random sampling from residual graphs |
| url | http://hdl.handle.net/1721.1/97225 https://orcid.org/0000-0002-0024-5847 |
| work_keys_str_mv | AT kargerdavidr fastaugmentingpathsbyrandomsamplingfromresidualgraphs AT levinematthews fastaugmentingpathsbyrandomsamplingfromresidualgraphs |