Optimizing cost flows by edge cost and capacity upgrade
| Autor: | Hartmut Noltemeier, Hans-Christoph Wirth, Ingo Demgensky |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Mathematical optimization
Polynomial Minimum cost flow Approximation algorithm Transportation problems Flow network Multi-commodity flow problem Theoretical Computer Science Network planning and design Series-parallel graphs Flow (mathematics) Computational Theory and Mathematics Network upgrade Discrete Mathematics and Combinatorics Minimum-cost flow problem Circulation problem Network design Mathematics |
| Zdroj: | Journal of Discrete Algorithms. 2(4):407-423 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2004.04.003 |
| Popis: | We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost. The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ , e >0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+ δ and 1+ e , respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/( δe ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect