Combinatorial approximation algorithms for buy-at-bulk connected facility location problems

详细信息    查看全文

• 作者：Andreas Bley^a ; ^{andreas.bley@mathematik.uni-kassel.de" class="auth_mail" title="E-mail the corresponding author} ; Mohsen Rezapour^b ; ^{rezapour@ualberta.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Connected facility location ; Buy-at-bulk network design ; Approximation algorithm ; Telecommunications
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：34-46
• 全文大小：455 K

文摘

We consider generalizations of the connected facility location problem, where clients connect to open facilities via access trees that are shared by multiple clients. For each edge of these trees, a combination of several cable types can be chosen, according to the demand carried by the edge. The task is to choose open facilities, a Steiner tree among them as a core network, and access trees with appropriate cable types on their edges to connect clients to the open facilities in such a way that the sum of the facility opening costs and cable costs for the core and access networks is minimal. Problems of this type arise widely in the planning of access and distribution networks in telecommunications, logistics, or energy networks.

In this paper, we introduce and analyze two fundamental versions of these problems. In the Buy-at-Bulk version of the problem, each access cable type has a fixed setup cost and a fixed capacity, whereas in the Deep-Discount problem version, each cable type has unlimited capacity but a traffic-dependent variable cost in addition to its fixed setup cost. We derive the first constant-factor approximation algorithms for these problems, using different algorithmic and analytical techniques.