The Library
A multi-exchange local search algorithm for the capacitated facility location problem - (Extended abstract)
Tools
UNSPECIFIED (2004) A multi-exchange local search algorithm for the capacitated facility location problem - (Extended abstract). In: 10th International Integer Programming and Combinatorial Optimization Conference, New York, NY, JUN 07-11, 2004. Published in: INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 3064 pp. 219-233. ISBN 3-540-22113-1. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We present a multi-exchange 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 + 2root2 - epsilon and 3 + 2 root2 + epsilon for any given constant epsilon > 0. Previously known best approximation ratio for the CFLP is 7.88, due to Mahdian and Pal (2003), based on the operations proposed by Pal, Tardos and Wexler (2001). Our upper bound 3 + 2root2 + epsilon also matches the best known ratio, obtained by Chudak and Williamson (1999), 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: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-22113-1 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Bienstock, D and Nemhauser, G | ||||
Official Date: | 2004 | ||||
Dates: |
|
||||
Volume: | 3064 | ||||
Number of Pages: | 15 | ||||
Page Range: | pp. 219-233 | ||||
Publication Status: | Published | ||||
Title of Event: | 10th International Integer Programming and Combinatorial Optimization Conference | ||||
Location of Event: | New York, NY | ||||
Date(s) of Event: | JUN 07-11, 2004 |
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 |