Geometric algorithms for a minimum cost assignment problem

Abstract

We consider the minimum cost A-assignment problem, which is equivalent to the minimum weight one-to-many matching problem in a complete bipartite graph Γ = (A,B), where A and B have n and k nodes respectively. Formulating the problem as a geometric problem, we give an O(kn + k3.5n0.5)-time randomized algorithm, which is better than existing O(kn2 + n2 log n)-time algorithm if k≤ n0.6.