ISSN:
1436-4646
Schlagwort(e):
Strongly polynomial time
;
Network flows
;
Generalized network flows
;
Generalized circulation
;
Generalized transhipment
;
Bidirected generalized networks
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract This paper, of which a preliminary version appeared in ISTCS'92, is concerned with generalized network flow problems. In a generalized network, each edgee = (u, v) has a positive ‘flow multiplier’a e associated with it. The interpretation is that if a flow ofx e enters the edge at nodeu, then a flow ofa e x e exits the edge atv. The uncapacitated generalized transshipment problem (UGT) is defined on a generalized 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 find a flow such that the excess or deficit 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 flow is minimized. Adler and Cosares [Operations Research 39 (1991) 955–960] 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 by the authors in [SIAM Journal on Computing, to appear result in a faster algorithm for restricted UGT. Generalized circulation is defined on a generalized network with demands at the nodes and capacity constraints on the edges (i.e., upper bounds on the amount of flow). The goal is to find a flow such that the excesses at the nodes are proportional to the demands and maximized. We present a new algorithm that solves the capacitated generalized flow problem by iteratively solving instances of UGT. The algorithm can be used to find an optimal flow or an approximation thereof. When used to find a constant factor approximation, the algorithm is not only more efficient than previous algorithms but also strongly polynomial. It is believed to be the first strongly polynomial approximation 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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01582579
Permalink
