Auction-Based Allocation of Location-Specific Tasks

We consider a task allocation problem in which agents and tasks have locations, and the goal is to allocate tasks among agents so as to minimise the distance travelled. We analyse two important algorithms under a generalised setting that puts additional feasibility constraints on allocations. We provide matching lower and upper bounds on the approximation guarantees achieved by the algorithms. We then conduct an experimental analysis of the relative performance of the algorithms. Our results indicate the relative performance of the algorithms as well as the effect of feasibility constraints on the guarantees of the algorithms.