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 .
Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time.
To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.
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.
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be
solved in polynomial time. The weighted matching problem is to find a matching in an
edge weighted graph that has maximum weight. The first polynomial time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O(nm + n2 log n). Many real world problems require graphs of such large size that this running time is too costly. Therefore there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3 . This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest but because it is easy to implement and the constants involved are quite small it is also useful in practice.
The terminal Steiner tree problem is a special version of
the Steiner tree problem, where a Steiner minimum tree has to be found
in which all terminals are leaves. We prove that no polynomial time approximation
algorithm for the terminal Steiner tree problem can achieve
an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial
time algorithms. Moreover, we present a polynomial time
approximation algorithm for the metric version of this problem with a performance
ratio of 2 , where denotes the best known approximation ratio
for the Steiner tree problem. This improves the previously best known
approximation ratio for the metric terminal Steiner tree problem of +2.