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 (ⅰ) any pair of vertices in C* is adjacent in H* where C* (∈) V and |C*| < p; (ⅱ) any pair of vertices in V C* is not adjacent in H*; (ⅲ) each v ∈ V C* is adjacent to exactly one vertex in C*; and (ⅳ) the routing cost r(H*) = Σ_(u,v∈V) dH* (u, v) is minimized where d_H?(u,v) = w(u,f*(u)) + w(f*(u),f*(v)) + w(v,f*(v)) and f* (u),f*(v) are the vertices in C* adjacent to u and v in H*, respectively. Note that w(v,f*(v)) = 0 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(n~2) for any β > 1/2 where n is the number of vertices in the input graph.
展开▼
