Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.ejor.2007.01.010
Title: A k-product uncapacitated facility location problem
Authors: Huang, H.-C. 
Li, R.
Keywords: Approximation algorithms
Computational complexity
Facility location
Heuristic
k-Product
Issue Date: 1-Mar-2008
Source: Huang, 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
Abstract: A 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.
Source Title: European Journal of Operational Research
URI: http://scholarbank.nus.edu.sg/handle/10635/54293
ISSN: 03772217
DOI: 10.1016/j.ejor.2007.01.010
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

10
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

9
checked on Nov 22, 2017

Page view(s)

37
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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