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 non-negative 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 city-to-airport 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 two-dimensional 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 non-uniform opening costs in the general metric, with the airport capacity (1+α)k where 0 < α ≤ 1, a (2+k/{k-1}+ε)-approximation algorithm and a bicriteria QPTAS for the same problem in the Euclidean plane. In this work, we give a Quasi-Polynomial-Time 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 minor-free graphs, and (2+k/{k-1})(1+ε)-approximation for AR with non-uniform opening costs for the aforementioned metrics. For general metrics, we give a 2-approximation for AR with a uniform opening cost in the strict setting of the problem, and an O(log n)-approximation for AR with non-uniform opening cost.

• Subjects / Keywords

  • Approximation algorithm
  • Airport and Railway Problem

• Graduation date

  Spring 2024

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-xrz6-k852

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial 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.