direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2012

Approximation algorithms for connected facility location with buy-at-bulk edge costs
Zitatschlüssel Report-028-2012
Autor Andreas Bley, Mehdi Hashemi, Mohsen Rezapour
Jahr 2012
Nummer 028
Zusammenfassung 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.
Link zur Publikation Download Bibtex Eintrag