Linear time local improvements for weighted matchings in graphs

Tools

Drake, D.E. ORCID: 0000-0001-8767-4355 and Hougardy, S., 2003. Linear time local improvements for weighted matchings in graphs. In: K. Jansen, M. Margraf, M. Mastrolilli and J.D.P. Rolim, eds., Experimental and efficient algorithms: Second International Workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003, Proceedings. Lecture Notes in Computer Science (2647). Berlin: Springer, pp. 107-119. ISBN 9783540402053

Full text not available from this repository.

Official URL: https://doi.org/10.1007/3-540-44867-5_9

Abstract

Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested. 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.

Item Type:

Chapter in book

Description:

Paper presented at Second International Workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003.

Creators:

Drake, D.E. and Hougardy, S.

Publisher:

Springer

Place of Publication:

Berlin

Date:

13 May 2003