An International Publisher for Academic and Scientific Journals
Author Login
Scholars Journal of Engineering and Technology | Volume-5 | Issue-01
An Approximation Algorithms for Facility Location Problems with Multi-type Clients
Xiaofang Luo, Yifei Yang, Zhijun Luo, Lisheng Wang
Published: Jan. 29, 2017 |
139
107
DOI: 10.21276/sjet.2017.5.1.4
Pages: 18-21
Downloads
Abstract
A new model of facility location problem referred to as a facility location problem with diverse type of
customers was proposed. The problem can be described as follows: There is a set of clients and a set of potential sites
where facilities of uncapacitated can be set up. Each client demands to be satisfied by a set of facilities depending on
which products it needs of the model, and one facility can be set up to supply only one product. Suppose that these
facilities considered are relatively centralized ,under the assumption that the setting costs is zero and the shipping costs
are in facilities centered metric space, it shows that the problem is NP-complete when k=2. Furthermore, an
approximation algorithm is presented, worst case performance ratio was proved to be below 2-1/k for any integer k.