direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publications

Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections
Zitatschlüssel MatuschkeBleyMüller2013
Autor Matuschke, Jannik and Bley, Andreas and Müller, Benjamin
Buchtitel Algorithms – ESA 2013
Seiten 707-718
Jahr 2013
Jahrgang 8125
Verlag Springer
Serie Lecture Notes in Computer Science
Zusammenfassung 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.
Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.