TY - GEN A1 - Drake, Doratha E. A1 - Hougardy, Stefan T1 - Improved Linear Time Approximation Algorithms for Weighted Matchings N2 - The weighted matching problem is to find a matching in a weighted graph that has maximum weight. The fastest known algorithm for this problem has running time O(nm +n2 log n). Many real world problems require graphs of such large size that this running time is too costly. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio of 2 3 ???? ". This improves the previously best performance ratio of 1 2 . Y1 - 2004 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/120 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-1208 ER -