Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem
Please always quote using this URN:urn:nbn:de:0296-matheon-12178
- We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of � ber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of in� nite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of in� nite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities su� ce to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
Author: | Andreas Bley, S. M. Hashemi, Mohsen Rezapour |
---|---|
URN: | urn:nbn:de:0296-matheon-12178 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2013/05/27 |
Release Date: | 2013/05/27 |
Tag: | approximation algorithm; combinatorial optimization; connected facility location |
Institute: | Research Center Matheon |
Technische Universität Berlin | |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization |
Preprint Number: | 1014 |