Some Recent Advances in Network Flows
The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity on the algorithmic aspects of network flow problems over the past few years has been pa...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5184 |
| _version_ | 1826211749683003392 |
|---|---|
| author | Ahuja, Ravindra K., 1956- Magnanti, Thomas L. Orlin, James B., 1953- |
| author_facet | Ahuja, Ravindra K., 1956- Magnanti, Thomas L. Orlin, James B., 1953- |
| author_sort | Ahuja, Ravindra K., 1956- |
| collection | MIT |
| description | The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity on the algorithmic aspects of network flow problems over the past few years has been particularly striking. Several techniques have proven to be very successful in permitting researchers to make these recent contributions: (i) scaling of the problem data; (ii) improved analysis of algorithms, especially amortized average case performance and the use of potential functions; and (iii) enhanced data structures. In this survey, we illustrate some of these techniques and their usefulness in developing faster network flow algorithms. Our discussion focuses on the design of faster algorithms from the worst case perspective and we limit our discussion to the following fundamental problems: the shortest path problem, the maximum flow problem, and the minimum cost flow problem. We consider several representative algorithms from each problem class including the radix heap algorithm for the shortest path problem, preflow push algorithms for the maximum flow problem, and the pseudoflow push algorithms for the minimum cost flow problem. |
| first_indexed | 2024-09-23T15:10:31Z |
| format | Working Paper |
| id | mit-1721.1/5184 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:10:31Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51842019-04-12T08:06:57Z Some Recent Advances in Network Flows Ahuja, Ravindra K., 1956- Magnanti, Thomas L. Orlin, James B., 1953- The literature on network flow problems is extensive, and over the past 40 years researchers have made continuous improvements to algorithms for solving several classes of problems. However, the surge of activity on the algorithmic aspects of network flow problems over the past few years has been particularly striking. Several techniques have proven to be very successful in permitting researchers to make these recent contributions: (i) scaling of the problem data; (ii) improved analysis of algorithms, especially amortized average case performance and the use of potential functions; and (iii) enhanced data structures. In this survey, we illustrate some of these techniques and their usefulness in developing faster network flow algorithms. Our discussion focuses on the design of faster algorithms from the worst case perspective and we limit our discussion to the following fundamental problems: the shortest path problem, the maximum flow problem, and the minimum cost flow problem. We consider several representative algorithms from each problem class including the radix heap algorithm for the shortest path problem, preflow push algorithms for the maximum flow problem, and the pseudoflow push algorithms for the minimum cost flow problem. 2004-05-28T19:26:58Z 2004-05-28T19:26:58Z 1989-10 Working Paper http://hdl.handle.net/1721.1/5184 en_US Operations Research Center Working Paper;OR 203-89 4937041 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Ahuja, Ravindra K., 1956- Magnanti, Thomas L. Orlin, James B., 1953- Some Recent Advances in Network Flows |
| title | Some Recent Advances in Network Flows |
| title_full | Some Recent Advances in Network Flows |
| title_fullStr | Some Recent Advances in Network Flows |
| title_full_unstemmed | Some Recent Advances in Network Flows |
| title_short | Some Recent Advances in Network Flows |
| title_sort | some recent advances in network flows |
| url | http://hdl.handle.net/1721.1/5184 |
| work_keys_str_mv | AT ahujaravindrak1956 somerecentadvancesinnetworkflows AT magnantithomasl somerecentadvancesinnetworkflows AT orlinjamesb1953 somerecentadvancesinnetworkflows |