Refine
Year of publication
Document Type
- ZIB-Report (18)
- In Proceedings (9)
- Article (2)
- Doctoral Thesis (1)
- In Collection (1)
Is part of the Bibliography
- no (31)
Keywords
Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
(2013)
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.