Premium
Geometric algorithms for the minimum cost assignment problem
Author(s) -
Tokuyama Takeshi,
Nakano Jun
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 0-89791-426-0
DOI - 10.1002/rsa.3240060403
Subject(s) - bipartite graph , combinatorics , mathematics , matching (statistics) , minimum weight , binary logarithm , assignment problem , graph , algorithm , discrete mathematics , statistics
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 .