On the flow cost lowering problem
| Autor: | Hartmut Noltemeier, Hans-Christoph Wirth, Ingo Demgensky |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Polynomial time approximation algorithm
Mathematical optimization Information Systems and Management General Computer Science Management Science and Operations Research Flow network Industrial and Manufacturing Engineering Multi-commodity flow problem Arc (geometry) Series-parallel graph Upgrade Flow (mathematics) Modeling and Simulation Minimum-cost flow problem Mathematics |
| Zdroj: | European Journal of Operational Research. 137:265-271 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/s0377-2217(01)00208-9 |
| Popis: | This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost on each arc by upgrading the arc. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series–parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series–parallel graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect