A Simple Approximation Algorithm for the Weighted Matching Problem
Please always quote using this URN:urn:nbn:de:0296-matheon-1228
- We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259–269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.
Author: | Doratha E. Drake, Stefan Hougardy |
---|---|
URN: | urn:nbn:de:0296-matheon-1228 |
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: | 151 |