TY - GEN A1 - Drake, Doratha E. A1 - Hougardy, Stefan T1 - A Simple Approximation Algorithm for the Weighted Matching Problem N2 - 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. Y1 - 2004 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/122 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-1228 ER -