• search hit 2 of 4
Back to Result List

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.

Download full text files

Export metadata

Additional Services

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