Filtern
Erscheinungsjahr
- 2013 (1)
Dokumenttyp
- Konferenzbeitrag (1)
Sprache
- Englisch (1)
Volltext vorhanden
- nein (1)
Gehört zur Bibliographie
- nein (1)
Institut
- Mathematical Optimization Methods (1) (entfernen)
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.