Please use this identifier to cite or link to this item:
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.
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2015.10.003 Discrete Optimization
Appears in Collections:Journal/Magazine Article

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

Page view(s)

Last Week
Last month
Citations as of May 21, 2018

Google ScholarTM



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