Refine
Year of publication
- 2013 (1)
Document Type
- In Proceedings (1)
Language
- English (1)
Has Fulltext
- no (1)
Is part of the Bibliography
- no (1)
Institute
- Mathematical Optimization Methods (1) (remove)
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.