The Library
A multiexchange local search algorithm for the capacitated facility location problem
Tools
UNSPECIFIED (2005) A multiexchange local search algorithm for the capacitated facility location problem. MATHEMATICS OF OPERATIONS RESEARCH, 30 (2). pp. 389-403. doi:10.1287/moor.1040.0125 ISSN 0364-765X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1287/moor.1040.0125
Abstract
We present a multiexchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2 root 2- epsilon and 3 + 2 root 2- + epsilon for any given constant epsilon > 0. The previously known best approximation ratio for the CFLP is 7.88, as shown by Mahdian and Pal (2003. Universal facility location. Proc. 11th Annual Eur. Sympos. Algorithms (ESA), 409-421), based on the operations proposed by Pal et al. (2001. Facility location with hard capacities. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (FOCS), 329-338). Our upper bound 3+2 root 2-+epsilon also matches the best-known ratio, obtained by Chudak and Williamson (1999. Improved approximation algorithm for capacitated facility location problems. Proc. 7th Conf Integer Programming Combin. Optim. (IPCO), 99-113), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pal et al. and techniques from the area of parallel machine scheduling.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management Q Science > QA Mathematics |
||||
Journal or Publication Title: | MATHEMATICS OF OPERATIONS RESEARCH | ||||
Publisher: | INST OPERATIONS RESEARCH MANAGEMENT SCIENCES | ||||
ISSN: | 0364-765X | ||||
Official Date: | May 2005 | ||||
Dates: |
|
||||
Volume: | 30 | ||||
Number: | 2 | ||||
Number of Pages: | 15 | ||||
Page Range: | pp. 389-403 | ||||
DOI: | 10.1287/moor.1040.0125 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |