Improved hardness and approximation results for single allocation hub location problems

Abstract Given a metric graph G = ( V , E , w ) and an integer k, we aim to find a single allocation k-hub location, which is a spanning subgraph consisting of a clique of size k such that every node outside of the clique is adjacent to exactly one node inside the clique. For various objective functions studied in the literature, we present improved hardness and approximation results.