Approximation Algorithms for a Capacitated Network Design Problem |
| |
Authors: | Refael
Hassin R
Ravi and F Sibel
Salman |
| |
Affiliation: | (1) Department of Statistics and Operations Research, Tel Aviv University, Tel Aviv 69978, Israel;(2) GSIA, Carnegie Mellon University, Pittsburgh, PA 15213, USA;(3) Krannert School of Management, Purdue University, West Lafayette, IN 47907, USA |
| |
Abstract: | We study a capacitated network design problem with applications in
local access network design. Given a network, the problem is to route
flow from several sources to a sink and to install
capacity on the edges to support the flow at minimum cost.
Capacity can be purchased only in multiples of a fixed quantity.
All the flow from a source must be routed
in a single path to the sink. This NP-hard problem generalizes the
Steiner tree problem and also more effectively models the applications
traditionally formulated as capacitated tree problems. We present
an approximation algorithm with performance ratio
(ρST + 2) where ρST is the performance ratio of
any approximation algorithm for the minimum Steiner tree problem.
When all sources have unit demand, the ratio
improves to ρST + 1) and, in particular, to 2 when all nodes
in the graph are sources. |
| |
Keywords: | Network design Approximation algorithms Routing flow Capacity installation |
本文献已被 SpringerLink 等数据库收录! |
|