LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
| Autor: | Mohsen Rezapour, José A. Soto, Mohammad R. Salavatipour, Zachary Friggstad |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Access network General Computer Science Linear programming Computer science Applied Mathematics 0211 other engineering and technologies Core network Approximation algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Steiner tree problem Facility location problem Computer Science Applications Network planning and design symbols.namesake 010201 computation theory & mathematics symbols Routing (electronic design automation) |
| Zdroj: | Algorithmica. 81:1075-1095 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-018-0458-x |
| Popis: | We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from K different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar [IPCO 2002] for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of O(K), and for the connected version, we get an improved bound of O(1). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink