  The multi allocation p-hub median problem (MApHM), the multi allocation
uncapacitated hub location problem (MAuHLP) and the multi allocation p-hub
location problem (MApHLP) are common hub location problems with several
practical applications. HLPs aim to construct a network for routing tasks
between different locations. Specifically, a set of hubs must be chosen and
each routing must be performed using one or two hubs as stopovers. The costs
between two hubs are discounted. The objective is to minimize the total
transportation cost in the MApHM and additionally to minimize the set-up costs
for the hubs in the MAuHLP and MApHLP. In this paper, an approximation
algorithm to solve these problems is developed, which improves the
approximation bound for MApHM to 3.451, for MAuHLP to 2.173 and for MApHLP to
4.552 when combined with the algorithm of Benedito & Pedrosa.
  The proposed algorithm is capable of solving much bigger instances than any
exact algorithm in the literature. New benchmark instances have been created
and published for evaluation, such that HLP algorithms can be tested and
compared on huge instances. The proposed algorithm performs on most instances
better than the algorithm of Benedito & Pedrosa, which was the only known
approximation algorithm for these problems by now.
