Approximating connected facility location with buy-at-bulk edge costs via random sampling
Please always quote using this URN:urn:nbn:de:0296-matheon-12164
- In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of in� nite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities su� ce to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.
Author: | Andreas Bley, Mohsen Rezapour |
---|---|
URN: | urn:nbn:de:0296-matheon-12164 |
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; connected facility location; network design |
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: | 1013 |