Please use this identifier to cite or link to this item:
Title: A k-product uncapacitated facility location problem
Authors: Huang, H.-C. 
Li, R.
Keywords: Approximation algorithms
Computational complexity
Facility location
Issue Date: 1-Mar-2008
Citation: 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.
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
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.


checked on Apr 5, 2020


checked on Mar 19, 2020

Page view(s)

checked on Mar 31, 2020

Google ScholarTM



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