License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.5
URN: urn:nbn:de:0030-drops-85183
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8518/
Adamaszek, Anna ;
Antoniadis, Antonios ;
Kumar, Amit ;
Mömke, Tobias
Approximating Airports and Railways
Abstract
In this paper we consider the airport and railway problem (AR), which combines capacitated facility location with network design, both in the general metric and the two-dimensional Euclidean space. An instance of the airport and railway problem consists of a set of points in the corresponding metric, together with a non-negative weight for each point, and a parameter k. The points represent cities, the weights denote costs of opening an airport in the corresponding city, and the parameter k is a maximum capacity of an airport. The goal is to construct a minimum cost network of airports and railways connecting all the cities, where railways correspond to edges connecting pairs of points, and the cost of a railway is equal to the distance between the corresponding points. The network is partitioned into components, where each component contains an open airport, and spans at most k cities. For the Euclidean case, any points in the plane can be used as Steiner vertices of the network. We obtain the first bicriteria approximation algorithm for AR for the general metric case, which yields a 4-approximate solution with a resource augmentation of the airport capacity k by a factor of 2. More generally, for any parameter 0 < p <= 1 where pk is an integer we develop a (4/3)(2 + 1/p)-approximation algorithm for metric AR with a resource augmentation by a factor of 1 + p.
Furthermore, we obtain the first constant factor approximation algorithm that does not resort to resource augmentation for AR in the Euclidean plane. Additionally, for the Euclidean setting we provide a quasi-polynomial time approximation scheme for the same problem with a resource augmentation by a factor of 1 + mu on the airport capacity, for any fixed mu > 0.
BibTeX - Entry
@InProceedings{adamaszek_et_al:LIPIcs:2018:8518,
author = {Anna Adamaszek and Antonios Antoniadis and Amit Kumar and Tobias M{\"o}mke},
title = {{Approximating Airports and Railways}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {5:1--5:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-062-0},
ISSN = {1868-8969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8518},
URN = {urn:nbn:de:0030-drops-85183},
doi = {10.4230/LIPIcs.STACS.2018.5},
annote = {Keywords: Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean}
}
|
Keywords: |
|
Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean |
|
Collection: |
|
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
27.02.2018 |
