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 twodimensional Euclidean space. An instance of the airport and railway problem consists of a set of points in the corresponding metric, together with a nonnegative 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 4approximate 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 quasipolynomial 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:15:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8518},
URN = {urn:nbn:de:0030drops85183},
doi = {10.4230/LIPIcs.STACS.2018.5},
annote = {Keywords: Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean}
}
2018
Keywords: 

Network Design, Facility Location, Approximation Algorithms, PTAS, Metric, Euclidean 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

2018 