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
Author:Jannik Matuschke, Andreas Bley, Benjamin Müller
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