Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ejor.2007.01.010
DC FieldValue
dc.titleA k-product uncapacitated facility location problem
dc.contributor.authorHuang, H.-C.
dc.contributor.authorLi, R.
dc.date.accessioned2014-06-16T09:29:35Z
dc.date.available2014-06-16T09:29:35Z
dc.date.issued2008-03-01
dc.identifier.citationHuang, H.-C., Li, R. (2008-03-01). A k-product uncapacitated facility location problem. European Journal of Operational Research 185 (2) : 552-562. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ejor.2007.01.010
dc.identifier.issn03772217
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/54293
dc.description.abstractA k-product uncapacitated facility location problem can be described as follows. There is a set of demand points where clients are located and a set of potential sites where facilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost determined by the product it intends to supply. There is a non-negative cost of shipping goods between each pair of locations. These costs are assumed to be symmetric and satisfy the triangle inequality. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, an approximation algorithm within a factor of 2 k + 1 of the optimum cost is presented. Assuming that fixed setup costs are zero, we give a 2 k - 1 approximation algorithm for the problem. In addition we show that for the case k = 2, the problem is NP-complete when the cost structure is general and there is a 2-approximation algorithm when the costs are symmetric and satisfy the triangle inequality. The algorithm is shown to produce an optimal solution if the 2-product uncapacitated facility location problem with no fixed costs happens to fall on a tree graph. © 2007 Elsevier B.V. All rights reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.ejor.2007.01.010
dc.sourceScopus
dc.subjectApproximation algorithms
dc.subjectComputational complexity
dc.subjectFacility location
dc.subjectHeuristic
dc.subjectk-Product
dc.typeArticle
dc.contributor.departmentINDUSTRIAL & SYSTEMS ENGINEERING
dc.description.doi10.1016/j.ejor.2007.01.010
dc.description.sourcetitleEuropean Journal of Operational Research
dc.description.volume185
dc.description.issue2
dc.description.page552-562
dc.description.codenEJORD
dc.identifier.isiut000250732600006
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

11
checked on Mar 27, 2020

WEB OF SCIENCETM
Citations

10
checked on Mar 19, 2020

Page view(s)

77
checked on Mar 22, 2020

Google ScholarTM

Check

Altmetric


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