An algorithm to solve them ×n assignment problem in expected timeO(mn logn)

DOI10.1002/net.3230100205zbMath0441.68076OpenAlexW1993343369MaRDI QIDQ3883530

Richard M. Karp

Publication date: 1980

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230100205

zbMATH Keywords

assignment problempriority queuesedge costs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A shortest augmenting path algorithm for dense and sparse linear assignment problems, Average complexity of divide-and-conquer algorithms, MetaCoAG: binning metagenomic contigs via composition, coverage and assembly graphs, The random linear bottleneck assignment problem, A BRANCH-AND-BOUND ALGORITHM FOR FINDING ALL OPTIMAL SOLUTIONS OF THE ASSIGNMENT PROBLEM, Recent developments in information-based complexity, Random assignment problems, Selected topics on assignment problems, A comparison of two algorithms for the assignment problem, Average case optimality

Cites Work

• Unnamed Item