5268
2013
eng
707
718
Algorithms -- ESA 2013
conferenceobject
Springer
0
--
--
--
Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings.
10.1007/978-3-642-40450-4_60
Lecture Notes in Computer Science
yes
Hans L. Bodlaender
Benjamin Müller
Jannik Matuschke
Giuseppe F. Italiano
Andreas Bley
Benjamin Müller
Mathematical Optimization
Mathematical Optimization Methods
Müller, Benjamin
no-project