GEOMETRIC ALGORITHMS FOR THE MINIMUM-COST ASSIGNMENT PROBLEM

被引：13

作者：

TOKUYAMA, T

NAKANO, J

机构：

[1] Tokyo Research Laboratory, Yamato, Kanagawa, 242, 1623‐14, Shimo‐tsuruma

来源：

RANDOM STRUCTURES & ALGORITHMS | 1995年 / 6卷 / 04期

关键词：

D O I：

10.1002/rsa.3240060403

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We consider the minimum-cost h-assignment problem, which is equivalent to the minimum-weight one-to-many matching problem on a complete bipartite graph Gamma = (A, B), where A and B have n and k nodes (n greater than or equal to 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. (C) 1995 John Wiley & Sons, Inc.

引用

页码：393 / 406

页数：14

共 13 条

[1] IMPROVED ALGORITHMS FOR BIPARTITE NETWORK FLOW [J].