LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
Artículo
![Thumbnail](/themes/Mirage2/images/cubierta.jpg)
Open/ Download
Publication date
2019Metadata
Show full item record
Cómo citar
Friggstad, Zachary
Cómo citar
LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design
Abstract
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 the first LP-based bound of O(1).
Indexation
Artículo de publicación SCOPUS
Identifier
URI: https://repositorio.uchile.cl/handle/2250/169707
DOI: 10.1007/s00453-018-0458-x
ISSN: 14320541
01784617
Quote Item
Algorithmica, Volumen 81, Issue 3, 2019, Pages 1075-1095
Collections