Improved Linear Time Approximation Algorithms for Weighted Matchings
Please always quote using this URN:urn:nbn:de:0296-matheon-1208
- 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 .
Author: | Doratha E. Drake, Stefan Hougardy |
---|---|
URN: | urn:nbn:de:0296-matheon-1208 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2004/09/19 |
Release Date: | 2004/04/19 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 149 |