Approximation guarantees for Hub Covering Problems
Florian Jaehn, Niklas Jost · 2025
Read Approximation guarantees for Hub Covering Problems by Florian Jaehn, Niklas Jost (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02566.txt.
Introduction
Florian Jaehn and Niklas Jost give the first systematic study of approximation for hub covering problems. Such problems choose hub sites so that delivery paths between origin and destination pairs pass through one or two hubs. Total setup cost is minimized, and path length limits must hold in one of two forms.
Hub problems arise in urban planning, cargo and airline networks, telecom systems, and e-mobility. The authors build a hierarchy that shows which variants are special cases of others. For four variants they give a polynomial time approximation algorithm. For the other eight variants, they prove that deciding whether any solution exists cannot be done in polynomial time unless a major complexity conjecture fails.
Catalog record
| CREATOR | Florian Jaehn, Niklas Jost |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02566
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximation guarantees for Hub Covering Problems Florian Jaehn, Niklas Jost Abstract Hub Covering Problems are a subclass of Hub Location Problems. The objective is to select a set of hubs that enable paths between given origin-destination delivery tasks, while minimizing the total setup cost of the hubs. Two constraints must be satisfied: each path must include one or two hubs, and depending on the problem variant, the total path length or the length of the longest edge must not exceed prescribed limits. Such problems arise in a variety of practical applications, including urban planning, cargo delivery systems, airline networks, telecommunication networks, and e-mobility. Although Hub Covering Problems are especially important from a practical point of view, no systematic study of their approximability exists. In particular, it remains open whether some variants can be reduced to others in polynomial time, and no approximation bound is known. We close this gap by establishing a hierarchy among these problems, demonstrating that certain variants are indeed special cases of others. For four variants, we give a polynomial-time approximation algorithm, and for the other eight variants, we show that no polynomial-time algorithm can decide whether a solution exists unless P = N P P=NP . Keywords: Hub Location Problems, Approximation Algorithms, Combinatorial Optimization, Network Routing, Graph Optimization 1 Introduction Hub Location Problems (HLPs) are integrated location and routing problems in which a set of hub nodes must be selected to serve as intermediate points of paths between origin and destination nodes, referred to as branches . Special cases of HLPs are Hub Covering Problems (HCPs), where a coverage radius restricts either the total path distance between two branches, the distance of any used edge, or the distance between a branch and its designated hub, depending on the problem variant. This framework combines two essential aspects: (i) the consolidation and transfer of demand at hubs, which yield economies of scale, and (ii) coverage constraints, which ensure acceptable service levels. HCPs arise in any kind of logistic networks, such as distribution networks or communication networks, where coverage must satisfy legal, physical, or technical constraints within a combined location–routing framework. A real-world coverage constraint arises from working-hour regulations, where the distance of a driver’s tour is legally limited, as considered by Goel (2009) . Similarly, air transportation imposes range limits because aircraft can store only a finite amount of fuel; Oktal and Ozger (2013) demonstrate that such range constraints are crucial when designing hub and spoke networks for aircraft. Moreover, Esmizadeh et al. (2021) study hub networks that must preserve a cold chain: if a tour exceeds the coverage limit, the dry ice melts, and the temperature constraint is violated. Devices such as access points, repeaters, routers, or transceivers transmit signals within a limited radius, naturally giving rise to coverage constraints. Meanwhile, traffic between sources and sinks uses a path through hub nodes, thereby reproducing the hub location structure (see Farahani et al. (2013) ). Recently, Bollapragada et al. (2023) modeled the design of wireline broadband access networks as an HLP, ensuring that every user remains within a feasible signal range while aggregating traffic through the hub network. Similarly, Funke et al. (2015) address the placement of electric-vehicle charging stations so that every demand location lies within a feasible battery range of at least one hub, with intermediate recharging enabling longer trips. These examples illustrate the dual coverage-plus-path structure. Comprehensive surveys of HLPs are provided by Alumur and Kara (2008) and Farahani et al. (2013) . Coverage-based hub formulations were first introduced by Campbell (1994) , whose variants form the foundation of the present study. Afterwards, Kara and Tansel (2003) developed formulations and linearizations for HCPs, while Wagner (2008) improved these formulations. Approximation algorithms exist only for HLP variants without coverage constraints, such as those proposed by Benedito and Pedrosa (2019) , Jost and Clausen (2023) , and Jost (2025) , which reduce HLPs to the Facility Location Problem. This reduction does not extend to HCPs due to their strict coverage limits. This raises the question which approximation bounds can be achieved by polynomial-time HCP algorithms and which algorithmic techniques may yield them. Approximation results are well established for classical covering problems closely related to HCPs. For the set covering problem, Chvátal (1979) proposed a greedy O(\log n) (using standard asymptotic notation) approximation algorithm, which Feige (1998) proved to be the best possible under \mathrm{P}\neq\mathrm{NP} . For the p -center problem, Hochbaum and Shmoys (1985) established a tight factor- 2 approximation (unless \mathrm{P}=\mathrm{NP} ). Extensions incorporating capacities or reliability constraints have been studied by Daskin (1997) . Although these models lack origin-destination relations through hubs, we will show that the result of Feige (1998) can be transferred to HCPs. The remainder of the paper is organized as follows: Section 2 formally defines the HCPs. Section 3 presents approximation and hardness results. Section 4 discusses implications and directions for future research. 2 Preliminaries Problem Description We study twelve HCP variants following the definition of Campbell (1994) . We first describe the least restrictive one and derive the remaining ones by adding further constraints. We are given a weighted and undirected graph G=(\mathcal{B}\cup\mathcal{H},E,d) in which the node set \mathcal{B}\cup\mathcal{H} consists of branches \mathcal{B} and potential hubs \mathcal{H} . Every edge \{i,j\}\in E has a distance d_{ij}=d_{ji}\geq 0 . For each potential hub h\in\mathcal{H} , a setup cost c_{h}\geq 0 is given. There is a set \mathcal{W}\subseteq\mathcal{B}\times\mathcal{B} and each element (b,b^{\prime})\in\mathcal{W} defines an origin-destination (OD) delivery task . For notational convenience, we assume symmetry in the delivery tasks such that (b,b^{\prime})\in\mathcal{W}\Rightarrow(b^{\prime},b)\in\mathcal{W} . Without loss of generality, we assume that for each branch b\in\mathcal{B} , there is at least one OD delivery task (b,b^{\prime})\in\mathcal{W} . Finally, we are given a covering distance threshold \phi\in\mathbb{N} , and a maximum number of hubs m\in\mathbb{N} . The input data for each HCP considered in this paper is summarized in the following Table 1 . Table 1 : Parameters Symbol Domain Meaning G G=(\mathcal{B}\cup\mathcal{H},E,d) Graph \mathcal{B} - Set of Branches \mathcal{H} - Set of potential Hubs E - Edge set d_{ij} \mathbb{N}_{0} Distance between nodes i and j c_{h} \mathbb{N}_{0} Setup cost for potential hub h\in\mathcal{H} \mathcal{W} \mathcal{W}\subseteq\mathcal{B}\times\mathcal{B} Set of origin-destination delivery tasks \phi \mathbb{N} Coverage distance threshold m \mathbb{N} Upper bound on the number of open hubs For an OD delivery task (b,b^{\prime})\in\mathcal{W} , a path p_{b,b^{\prime}} is either a sequence of three vertices (b,h,b^{\prime}) with h\in\mathcal{H} , \{b,h\},\{h,b^{\prime}\}\in E or a sequence of four vertices (b,h,h^{\prime},b^{\prime}) with h,h^{\prime}\in\mathcal{H} , \{b,h\},\{h^{\prime},b^{\prime}\}\in E . Note that an edge \{h,h^{\prime}\} does not have to exist for the least restrictive variant. Without loss of generality, we assume \{h,h\}\in E for all h\in\mathcal{H} and d_{hh}=0 so that we can restrict ourselves to paths with four vertices in the following for every variant. The problem is to determine a path for each OD delivery task. Thus, a solution is a set P of paths such that P contains a path p_{b,b^{\prime}} for each OD delivery task (b,b^{\prime})\in\mathcal{W} . If a potential hub h\in\mathcal{H} is part of some path p\in P (by abuse of notation, we write h\in p ), we say that hub h is open . Thus, for a given solution P , the set of open hubs