Please use this identifier to cite or link to this item: https://doi.org/10.1057/jors.2012.31
Title: Heuristic algorithms for general k-level facility location problems
Authors: Li, R.
Huang, H.-C. 
Huang, J.
Keywords: computational complexity
facility location
heuristic
linear programming
NP-complete
optimization
Issue Date: Jan-2013
Source: Li, R., Huang, H.-C., Huang, J. (2013-01). Heuristic algorithms for general k-level facility location problems. Journal of the Operational Research Society 64 (1) : 106-113. ScholarBank@NUS Repository. https://doi.org/10.1057/jors.2012.31
Abstract: In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight. © 2013 Operational Research Society Ltd. All rights reserved.
Source Title: Journal of the Operational Research Society
URI: http://scholarbank.nus.edu.sg/handle/10635/63149
ISSN: 01605682
DOI: 10.1057/jors.2012.31
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

27
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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