AVERAGE-CASE ANALYSIS OF A HEURISTIC FOR THE ASSIGNMENT PROBLEM

Authors
KARP RM KAN AHGR VOHRA RV
Citation
Rm. Karp et al., AVERAGE-CASE ANALYSIS OF A HEURISTIC FOR THE ASSIGNMENT PROBLEM, Mathematics of operations research, 19(3), 1994, pp. 513-522
Citations number
11
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
Journal title
Mathematics of operations research → ACNP
ISSN journal
0364765X
Volume
19
Issue
3
Year of publication
1994
Pages
513 - 522
Database
ISI
SICI code
0364-765X(1994)19:3<513:AAOAHF>2.0.ZU;2-S
Abstract
Our main contribution is an O(n log n) algorithm that determines with high probability a perfect matching in a random 2-out bipartite graph. We also show that this algorithm runs in O(n) expected time. This alg orithm can be used as a subroutine in an O(n2) heuristic for the assig nment problem. When the weights in the assignment problem are independ ently and uniformly distributed in the interval [0, 1], we prove that the expected weight of the assignment returned by this heuristic is bo unded above by 3 + O(n(-a)), for some positive constant a.