In this paper, we present approximation algorithms for theAirport and Railwayproblem (AR) on several classes of graphs. The AR problem, introduced as reported byAdamaszek et al. (in: Ollinger, Vollmer (eds) 33rd symposium on theoretical aspectsof computer science (STACS 2016). Leibniz international proceedings in informatics(LIPIcs), Dagstuhl, 2016), is a combination of theCapacitated Facility Loca-tionproblem (CFL) and theNetwork Design Problem(NDP). An AR instanceconsists of a set of points (cities)Vin a metricd(., .), each of which is associatedwith a non-negative costfvand a numberk, which represent respectively the cost ofestablishing an airport (facility) in the corresponding point, and the universal airportcapacity. A feasible solution is a network of airports and railways providing servicesto all cities without violating any capacity, where railways are edges connecting pairsof 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 other words, find aforest, each component having at mostkpoints and one open facility, minimizing thetotal cost of edges and airport opening costs. As reported by Adamaszek et al. (in:Ollinger, Vollmer (eds) 33rd symposium on theoretical aspects of computer science(STACS 2016). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl,2016) presented a PTAS for AR in the two-dimensional Euclidean metricR2witha uniform opening cost. In subsequent work (as reported by Adamaszek et al. (in:Niedermeier, Vall & eacute;e (eds) 35th symposium on theoretical aspects of computer science(STACS 2018). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl,2018).) presented a bicriteria43(2+1 alpha)-approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1 + alpha, i.e.(1+alpha)k capacity where 0 < alpha <= 1, a(2 + k/k-1 + epsilon)-approximation algorithm and a bicrite-ria Quasi-Polynomial Time Approximation Scheme (QPTAS) for the same problem in the Euclidean planeR2. In this work, we give a 2-approximation for AR with auniform opening cost for general metrics and anO(logn)-approximation for non-uniform opening costs. We also give a QPTAS for AR with a uniform opening costin graphs of bounded treewidth and a QPTAS for a slightly relaxed version in thenon-uniform setting. The latter impliesO(1)-approximation on graphs of boundeddoubling dimensions, graphs of bounded highway dimensions and planar graphs inquasi-polynomial time.
