Parametric maximal flows in generalized networks – complexity and algorithms
作者:
G. Ruhe,
期刊:
Optimization
(Taylor Available online 1988)
卷期:
Volume 19,
issue 2
页码: 235-251
ISSN:0233-1934
年代: 1988
DOI:10.1080/02331938808843341
出版商: Akademic-Verlag
关键词: Network Flows;Generalized Networks;Complexity;parametric Optimization
数据来源: Taylor
摘要:
The problem of determining parametric maximal flows in networks with gains is considered. A worst-case analysis with respect to the number of breakpoints in the optimal objective value function is performed for both parametric flows leaving the source and parametric capacities of the arcs. The result is an exponential growth of the number of breakpoints depending on the number of vertices in the underlying graph. From there, the idea of a horizontal approximation algorithm developed from Hamachee and Foulds [5] is extended to generalized flows. In each iteration the horizontal approach makes an improvement which is a piecewise linear function of the whole parameter interval. This process can be applied up to optimality
点击下载:
PDF (689KB)
返 回