An incremental algorithm for the uncapacitated facility location problem
Please always quote using this URN:urn:nbn:de:0296-matheon-12192
- We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem. We seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. Our aim is to have the solution obtained for serving the first l customers in the sequence be competitive with the optimal solution to serve any l customers. We provide an incremental framework that provides an overall competitive factor of 8 and a worst case instance that provides the lower bound of 3. The problem has applications in multi-stage network planning.
Author: | Ashwin Arulselvan, Olaf Maurer, Martin Skutella |
---|---|
URN: | urn:nbn:de:0296-matheon-12192 |
Referee: | Rolf H. Möhring |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2013/05/28 |
Release Date: | 2013/05/28 |
Tag: | incremental algorithm, facility location problem, network design |
Institute: | Technische Universität Berlin |
MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Rxx Discrete mathematics in relation to computer science / 68R01 General |
Preprint Number: | 1016 |