 23 views
 23 downloads
Approximation Schemes for the Airport and Railway Problem

 Author / Creator
 Tian, Lijiangnan

In this thesis, we present approximation schemes for the airport and railway problem (AR) on several classes of graphs. The AR problem, introduced by Adamaszek et al., is a combination of the capacitated facility location problem (CFL) and the network design problem. An AR instance comprises a set of points, which are called cities, residing in some metrics, each of which is associated with a nonnegative cost and a number k, which represent respectively the cost of establishing an airport in the corresponding city, and the universal airport capacity.
A feasible solution is a network of airports and railways providing services to all cities without violating any capacity, where railways are edges connecting pairs of points, with their costs equivalent to the distance between the respective points. The objective is to find such a network with the least cost. In the strict setting, the network is divided into components, each with an open airport and a maximum of k cities. In a more relaxed setting of the problem, the railway paths heading to different airports are allowed to share edges, either the cost of each citytoairport path is paid separately, or the railways have a universal edge capacity k and one is allowed to use parallel edges (which is called AR'). Adamaszek et al. presented a PTAS for AR in the twodimensional Euclidean metric with a uniform opening cost in the strict setting. Adamaszek et al. presented a bicriteria 4/3 (2+1/α)approximation algorithm for AR with nonuniform opening costs in the general metric, with the airport capacity (1+α)k where 0 < α ≤ 1, a (2+k/{k1}+ε)approximation algorithm and a bicriteria QPTAS for the same problem in the Euclidean plane. In this work, we give a QuasiPolynomialTime Approximation Scheme (QPTAS) for AR with a uniform opening cost in graphs of bounded treewidth, QPTAS for AR' in graphs of bounded doubling dimensions, graphs of bounded highway dimensions and minorfree graphs, and (2+k/{k1})(1+ε)approximation for AR with nonuniform opening costs for the aforementioned metrics. For general metrics, we give a 2approximation for AR with a uniform opening cost in the strict setting of the problem, and an O(log n)approximation for AR with nonuniform opening cost.

 Subjects / Keywords

 Graduation date
 Spring 2024

 Type of Item
 Thesis

 Degree
 Master of Science

 License
 This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for noncommercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.