Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
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
Year of first publication:2013
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.