TY - GEN A1 - Bley, Andreas A1 - Rezapour, Mohsen T1 - Approximating connected facility location with buy-at-bulk edge costs via random sampling N2 - 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. KW - network design KW - connected facility location KW - approximation algorithm Y1 - 2013 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1216 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-12164 ER -