Paper Info
Title
Combinatorial approximation algorithms for buy-at-bulk connected facility location problems.
Abstract
We consider generalizations of the connected facility location problem, where clients connect to open facilities via access trees that are shared by multiple clients. For each edge of these trees, a combination of several cable types can be chosen, according to the demand carried by the edge. The task is to choose open facilities, a Steiner tree among them as a core network, and access trees with appropriate cable types on their edges to connect clients to the open facilities in such a way that the sum of the facility opening costs and cable costs for the core and access networks is minimal. Problems of this type arise widely in the planning of access and distribution networks in telecommunications, logistics, or energy networks.In this paper, we introduce and analyze two fundamental versions of these problems. In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. We derive the first constant-factor approximation algorithms for these problems, using different algorithmic and analytical techniques.
Year
DOI
Venue
2016
10.1016/j.dam.2016.05.016
Discrete Applied Mathematics
Keywords
Field
DocType
Connected facility location,Buy-at-bulk network design,Approximation algorithm,Telecommunications
Approximation algorithm,Mathematical optimization,Steiner tree problem,Core network,Computer science,Generalization,Distribution networks,Facility location problem,Variable cost,Access network
Journal
Volume
Issue
ISSN
213
C
0166-218X
Citations 
PageRank 
References 
0
0.34
17
Authors
2
Name
Order
Citations
PageRank
Andreas Bley1162.46
Mohsen Rezapour2384.76