Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43529
Title: Improved algorithms for joint optimization of facility locations and network connections
Authors: Lai, X
Xu, Z 
Keywords: Approximation algorithm
Facility location
Network connection
Polynomial time algorithm
Steiner forest
Issue Date: 2016
Publisher: Elsevier
Source: European journal of operational research, 2016, v. 250, no. 3, p. 745-753 How to cite?
Journal: European journal of operational research 
Abstract: This paper studies a k-median Steiner forest problem that jointly optimizes the opening of at most k facility locations and their connections to the client locations, so that each client is connected by a path to an open facility, with the total connection cost minimized. The problem has wide applications in the telecommunication and transportation industries, but is strongly NP-hard. In the literature, only a 2-approximation algorithm is known, it being based on a Lagrangian relaxation of the problem and using a sophisticated primal-dual schema. In this study, we have developed an improved approximation algorithm using a simple transformation from an optimal solution of a minimum spanning tree problem. Compared with the existing 2-approximation algorithm, our new algorithm not only achieves a better approximation ratio that is easier to be proved, but also guarantees to produce solutions of equal or better quality - up to 50 percent improvement in some cases. In addition, for two non-trivial special cases, where either every location contains a client, or all the locations are in a tree-shaped network, we have developed, for the first time in the literature, new algorithms that can solve the problem to optimality in polynomial time.
URI: http://hdl.handle.net/10397/43529
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2015.10.003 Discrete Optimization
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

32
Last Week
4
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.