TY - GEN A1 - Bley, Andreas A1 - Hashemi, S. M. A1 - Rezapour, Mohsen T1 - Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem N2 - 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. KW - combinatorial optimization KW - connected facility location KW - approximation algorithm Y1 - 2013 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1217 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-12178 ER -