Improved linear time approximation algorithms for weighted matchings

Drake, DE ORCID: https://orcid.org/0000-0001-8767-4355 and Hougardy, S, 2003. Improved linear time approximation algorithms for weighted matchings. In: Arora, S, Jansen, K, Rolim, JDP and Sahai, A, eds., Approximation, randomization, and combinatorial optimization. Algorithms and techniques: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approx. Lecture Notes in Computer Science . Berlin: Springer, pp. 14-23. ISBN 9783540407706; 9783540451983

Full text not available from this repository.

Abstract

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.

Item Type:	Chapter in book
Description:	Paper presented at the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003
Creators:	Drake, D.E. and Hougardy, S.
Publisher:	Springer
Place of Publication:	Berlin
Date:	2003
ISBN:	9783540407706; 9783540451983
Identifiers:	Number Type 10.1007/978-3-540-45198-3_2 DOI 1849512 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Jeremy Silvester
Date Added:	05 Jan 2024 10:27
Last Modified:	05 Jan 2024 10:27
URI:	https://irep.ntu.ac.uk/id/eprint/50628

Actions (login required)

Edit View

Statistics

Views

Downloads