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 105
- Downloads 0
Pattern Designing of Portfolio Management of Hydro Projects with Implementation of Multi-Criteria Models
Portfolio is a collection of projects, plans or activities which are managed integrally to facilitate the efficient management of works in order to reach the strategic goals. Portfolio management is one of the most impor...
Dynamic Response Research of the Framed Spherical Tank Seismic Subsructure with Liquid Sloshing
Abstract: In recent years, the frequency that the earthquakes occur shows a tendency of rising, and the importance of the seismic method is increasing gradually. Towering framed structure as a very important special stru...
Case Study of Earthworks Management on Hu-Shan Reservoir
Present study investigated the earthworks (storage and transportation) management on large scale project (Hu-Shan reservoir) performance (cost and time). After apply the planning structure which developed in present stud...
Failure early warning model for Electrical Submersible Pump based on regression analysis
Take 120 the Electrical Submersible Pump (ESP)well as the object of study, has constructed based on 6 commonly used target return early warning models, then to dives the Electrical Submersible Pump breakdown well to carr...
Study of Water Quality Of Malaprabha River Near Habbanatti, Belgaum, Karnataka
An attempt has been made to know the water quality of Malaprabha river of Belgaum near Habbanatti from June 2011 to May 2012. Water samples were collected and brought to the laboratory for analysis. Concentrations of...