A local search approximation algorithm for the uniform capacitated k-facility location problem

Lu Han (), Dachuan Xu (), Donglei Du () and Dongmei Zhang ()
Additional contact information
Lu Han: Beijing University of Technology
Dachuan Xu: Beijing University of Technology
Donglei Du: University of New Brunswick
Dongmei Zhang: Shandong Jianzhu University

Journal of Combinatorial Optimization, 2018, vol. 35, issue 2, No 7, 409-423

Abstract: 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: k-Facility location; Uniform capacitated; Approximation algorithm; Local search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0179-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0179-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0179-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().