<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5268</id>
    <completedYear/>
    <publishedYear>2013</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>707</pageFirst>
    <pageLast>718</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>Algorithms -- ESA 2013</volume>
    <type>conferenceobject</type>
    <publisherName>Springer</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections</title>
    <abstract language="eng">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.</abstract>
    <identifier type="doi">10.1007/978-3-642-40450-4_60</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <editor>Hans L. Bodlaender</editor>
    <submitter>Benjamin Müller</submitter>
    <author>Jannik Matuschke</author>
    <editor>Giuseppe F. Italiano</editor>
    <author>Andreas Bley</author>
    <author>Benjamin Müller</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="projects" number="no-project">no-project</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
