Name
Abstract | ||
|---|---|---|
This paper is concerned with generalized network ow problems In a generalized network each edge e u v has a positive ow multiplier a<SUB>e associated with it The interpretation is that if a ow of x<SUB>e enters the edge at node u then a ow of a<SUB>e,<SUB>e exits the edge at v The uncapacitated generalized transshipment problem UGT is de ned on a gen eralized network where demands and supplies real numbers are associated with the vertices and costs real numbers are associated with the edges The goal is to nd a ow such that the excess or de cit at each vertex equals the desired value of the supply or demand and the sum over the edges of the product of the cost and the ow is minimized Adler and Cosares reduced the restricted uncapacitated generalized transshipment problem where only demand nodes are present to a system of linear inequalities with two variables per inequality The algorithms presented in result in a faster algorithm for restricted UGT Generalized circulation is de ned on a generalized network with demands at the nodes and capacity constraints on the edges i e upper bounds on the amount of ow The goal is to nd a ow such that the excesses at the nodes are proportional to the demands and maximized We present a new algorithm that solves the capacitated generalized ow problem by iteratively solving instances of UGT The algorithm can be used to nd an optimal ow or an approximation thereof When used to nd a constant factor approximation the algorithm is not only more e cient than previous algorithms but also strongly polynomial It is believed to be the rst strongly polynomial approx imation algorithm for generalized circulation The existence of such an approximation algorithm is interesting since it is not known whether the exact problem has a strongly polynomial algorithm |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BF01582579 | Mathematical Programming |
Keywords | Field | DocType |
new algorithm,generalized network flow,demand and supply,network flow,upper bound | Flow network,Combinatorics,Computer science,Flow (psychology),Circulation problem,Polynomial algorithm,Minimum-cost flow problem | Journal |
Volume | Issue | ISSN |
64 | 3 | 1436-4646 |
ISBN | Citations | PageRank |
0-387-55553-6 | 17 | 2.14 |
References | Authors | |
10 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edith Cohen | 1 | 3260 | 268.21 |
| Nimrod Megiddo | 2 | 4244 | 668.46 |