Approximation algorithms for the airport and railway problem

Mohammad R. Salavatipour () and Lijiangnan Tian ()
Additional contact information
Mohammad R. Salavatipour: University of Alberta
Lijiangnan Tian: University of Alberta

Journal of Combinatorial Optimization, 2025, vol. 49, issue 1, No 8, 33 pages

Abstract: Abstract 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

Keywords: Facility location; Approximation algorithms; Dynamic programming (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01237-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:1:d:10.1007_s10878-024-01237-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01237-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().