Geometric algorithms for the minimum cost assignment problem
Takeshi Tokuyama, Jun Nakano · Random Structures and Algorithms · 1995
Abstract We consider the minimum‐cost λ‐assignment problem, which is equivalent to the minimum‐weight one‐to‐many matching problem on a complete bipartite graph Γ = ( A, B ), where A and B have n and k nodes ( n ⩾ k ), respectively. Formulating the problem geometrically, we given an O ( kn + k 2.5 n 0.5 log 1.5 n ) time randomized algorithm, which is better than the existing O ( kn 2 + n 2 log n ) time algorithm if n > k log k .