作者：TARJAN, RE
作者单位：Nokia Corporation; Nokia Bell Labs; AT&T
摘要：We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a bound of n(log n)/2 + O(1) on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented to run in n(log n)/2 + O(1) time. In the special case of planar graphs, we obtain a polynomial bound on the number of pivots and the running tim...
作者：GOLDBERG, AV; PLOTKIN, SA; TARDOS, E
作者单位：Stanford University; Cornell University
摘要：We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e)-gamma-(e) units arrive at the other end. For instance, nodes of the graph can correspond to different currencies, with the multipliers being the exchange rates. We require conservation of flow at every node except a given source node. The goal is to maximize the amount of flow excess at the source. Thi...
