Approximation algorithms for connected facility location with buy-at-bulk edge costs

Source file is available as :   Portable Document Format (PDF)

Author(s) : Andreas Bley , Mehdi Hashemi , Mohsen Rezapour

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 28-2012

MSC 2000

90C27 Combinatorial optimization
68W25 Approximation algorithms

Abstract :
We consider a generalization of the Connected Facility Location problem where clients may connect to open facilities via access trees shared by multiple clients. The task is to choose facilities to open, to connect these facilities by a core Steiner tree (of infinite capacity), and to design and dimension the access trees, such that the capacities installed on the edges of these trees suffice to simultaneously route all clients' demands to the open facilities. We assume that the available edge capacities are given by a set of different cable types whose costs obey economies of scale. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing capacities on the access tree edges. In this paper, we devise the first constant-factor approximation algorithm for this problem. We also present a factor 6.72 approximation algorithm for a simplified version of the problem where multiples of only one single cable type can be installed on the access edges.

Keywords : Approximation algorithms, Facility Location, Network Design