Approximation algorithms for the airport and railway problem

In this paper, we present approximation algorithms for the Airport and Railway problem (AR) on several classes of graphs. The $$\text{ AR }$$ AR problem, introduced 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), is a combination of the Capacitated Facility Location problem (CFL) and the Network Design Problem (NDP). An $$\text{ AR }$$ AR instance consists of a set of points (cities) V in a metric d(., .), each of which is associated with a non-negative cost $$f_v$$ f v and a number k, which represent respectively the cost of establishing an airport (facility) in the corresponding point, 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 other words, find a forest, each component having at most k points and one open facility, minimizing the total 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 $$\text{ AR }$$ AR in the two-dimensional Euclidean metric $$\mathbb {R}^2$$ R 2 with a uniform opening cost. In subsequent work (as reported by Adamaszek et al. (in: Niedermeier, Vallée (eds) 35th symposium on theoretical aspects of computer science (STACS 2018). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, 2018).) presented a bicriteria $$\frac{4}{3}\left( 2+\frac{1}{\alpha }\right) $$ 4 3 2 + 1 α -approximation algorithm for $$\text{ AR }$$ AR with non-uniform opening costs but violating the airport capacity by a factor of $$1+\alpha $$ 1 + α , i.e. $$(1+\alpha )k$$ ( 1 + α ) k capacity where $$0