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 112
- Downloads 0
The Design for Hardware in the Loop Simulation Test Bench
HIL (Hardware in the loop) simulation test bench was developed based on the CarSim and LabVIEW software. First of all, CarSim, Real-time vehicle dynamics software, was used to build parameterized model for vehicle. Secon...
Encryption Method of Gray Image Based on BP Neural Network
At present, the problem that exists in the gray image encryption is easy to be cracked. Aiming at it, this paper proposes a kind of encryption method based on BP neural network. This method uses the very strong nonlinear...
Empirical Study on the Main Physical Items of Nano Oil in an Isolated Vertical Pipe
Finding the properties of crude oil after addition of nano particle is considered in this work. Results are shown in Figures indicate on the positive effect of nano particles in the oil sweetening processes. The amount o...
Global Solutions to elastic string with weak damping by Renormalization Group Method Based on the Classical Theory of Envelope
By the renormalization group method based on the classical theory of envelope, the global approximate solution to damped Fisher equation is obtained. Keywords: renormalization group; envelope theory; global approximate s...
The investigation of sulfur absorption from sour gas in packed bed with carbon nano fluid
Many different processes are used to treat raw natural gas to pipeline quality. Sulfur is commonly present as an impurity in fossil fuels. The mechanism of sulfur absorption by nano fluid in a packed bed under the magnet...