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

DOI10.1002/NET.3230100205MaRDI QIDQ3883530zbMATH OpenOpenAlexFDO

Authors Richard 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 problemedge costspriority queues

Mathematics Subject Classification ID

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

Cited in

(10)

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

This page was built for publication: An algorithm to solve them ×n assignment problem in expected timeO(mn logn)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3883530)