An Approximation Algorithms for Facility Location Problems with Multi-type Clients
Journal Title: Scholars Journal of Engineering and Technology - Year 2017, Vol 5, Issue 1
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. Keywords: Facility Location Problem; Approximation algorithms; Complexity.
Authors and Affiliations
Xiaofang Luo, Yifei Yang, Zhijun Luo, Lisheng Wang
Keywords
Related Articles
- EP ID EP385446
- DOI -
- Views 100
- Downloads 0
Analyzing the Quality Management Process in Healthcare Sector
This paper is concerning the quality management in the two different private Erbil hospitals. The reason behind choosing this topic and those two different private hospitals is that they both are in same environment of p...
Antifungal Properties of Ozone Gas in Stored Naturally Contaminated Dry Maize (Zea mays L.) Grains
Antifungal properties of ozone (O3) gas were evaluated in stored naturally contaminated dry maize grains. An experimental design was applied at three concentrations (20, 40, 60 μmol/mol) and different exposure times (30...
On Special Diophantine Triples
This paper concerns with the study of constructing a special Diophantine triples (a,b,p) such that the product of any two elements of the set added with their sum and increased by a polynomial with integer coefficients i...
The Use of Gum Arabic as an Admixture in Concrete
This paper is the result of findings on the use of Gum Arabic as an admixture in concrete. The research seeks to find the effect of Gum Arabic on some properties of cement and concrete at both fresh and hardened states....
Air Drying Characteristics of Aerial Yam (Dioscorea bulbifera)
The study investigated the air drying characteristics of aerial yam in a fabricated air dryer within a temperature range of 50 to 70°C. Prior to drying, the sample was divided into two portions; one part was boiled at 10...