A complete weighted graph G = (V, E,w) is called Δβ-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. Given a Δβ -metric graph G = (V, E,w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C* ⊂ V and |C*|≤p; (ii) any pair of vertices in V\C* is not adjacent in H*; (iii) each v∈V\C* is adjacent to exactly one vertex in C*; and (iv) the routing cost (Formula Presented) is minimized where (Formula Presented) and f*(u),f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that (Formula Presented) if v∈C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Δβ-metric graphs for any β>1/2. Moreover, we give 2β-approximation algorithms running in time O(n2) for any β>1/2 where n is the number of vertices in the input graph.