• search hit 113 of 1103
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.