Linear time local improvements for weighted matchings in graphs

Drake, DE ORCID: https://orcid.org/0000-0001-8767-4355 and Hougardy, S, 2003. Linear time local improvements for weighted matchings in graphs. In: Jansen, K, Margraf, M, Mastrolilli, M and Rolim, JDP, 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.

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
Number:	2647
ISBN:	9783540402053
Identifiers:	Number Type 10.1007/3-540-44867-5_9 DOI 1849517 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Jeremy Silvester
Date Added:	05 Jan 2024 10:57
Last Modified:	05 Jan 2024 10:57
URI:	https://irep.ntu.ac.uk/id/eprint/50629

Actions (login required)

Edit View

Statistics

Views

Downloads