Geometric algorithms for the minimum cost assignment problem | Zendy

Tokuyama Takeshi | Zendy; Nakano Jun | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research