A local search approximation algorithm for the uniform capacitated k-facility location problem |
| |
Authors: | Lu Han Dachuan Xu Donglei Du Dongmei Zhang |
| |
Affiliation: | 1.Department of Information and Operations Research, College of Applied Sciences,Beijing University of Technology,Beijing,People’s Republic of China;2.Faculty of Business Administration,University of New Brunswick,Fredericton,Canada;3.School of Computer Science and Technology,Shandong Jianzhu University,Jinan,People’s Republic of China |
| |
Abstract: | In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|