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.
| Author: | Jannik Matuschke, Andreas Bley, Benjamin MüllerORCiD |
|---|---|
| Editor: | Hans L. Bodlaender, Giuseppe F. Italiano |
| Document Type: | In Proceedings |
| Volume: | Algorithms -- ESA 2013 |
| First Page: | 707 |
| Last Page: | 718 |
| Series: | Lecture Notes in Computer Science |
| Publisher: | Springer |
| Year of first publication: | 2013 |
| DOI: | https://doi.org/10.1007/978-3-642-40450-4_60 |
