Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Approximation algorithms for connected facility location with buy-at-bulk edge costs
Author(s): Bley, Andreas
Hashemi, Mehdi
Rezapour, Mohsen
Type: Research Paper
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.
Subject(s): approximation algorithms
facility location
network design
Issue Date: 28-Aug-2012
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68W25 Approximation algorithms
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2012, 28
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 303.78 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.