• search hit 3 of 3
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.