Loading...
Please wait, while we are loading the content...
Similar Documents
Faster scaling algorithms for network problems (1989)
| Content Provider | CiteSeerX |
|---|---|
| Author | Gabow, Harold N. Tarjan, Robert E. |
| Abstract | This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimumcost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in O(v/’rn log(nN)) time, where n, m, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. As in the work of Goldberg and Tarjan, in each scaled problem an approximate optimum solution is found, rather than an exact optimum. |
| File Format | |
| Volume Number | 18 |
| Journal | SIAM J. COMPUT |
| Language | English |
| Publisher Date | 1989-01-01 |
| Access Restriction | Open |
| Subject Keyword | Network Problem Assignment Problem Minimumcost Solution Transportation Problem Algorithm Work Bipartite Graph Minimum-cost Flow Problem Best-known Bound Minimum-cost Matching Approximate Optimum Solution Exact Optimum Rn Log Operation Research Corresponding Problem |
| Content Type | Text |
| Resource Type | Article |
