Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleHeuristic algorithms for general k-level facility location problems
dc.contributor.authorLi, R.
dc.contributor.authorHuang, H.-C.
dc.contributor.authorHuang, J.
dc.identifier.citationLi, 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.
dc.description.abstractIn 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.
dc.subjectcomputational complexity
dc.subjectfacility location
dc.subjectlinear programming
dc.contributor.departmentINDUSTRIAL & SYSTEMS ENGINEERING
dc.description.sourcetitleJournal of the Operational Research Society
Appears in Collections:Staff Publications

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

Page view(s)

checked on Mar 29, 2020

Google ScholarTM


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