๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A simple approximation algorithm for the weighted matching problem

โœ Scribed by Doratha E Drake; Stefan Hougardy

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
61 KB
Volume
85
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 [

๐Ÿ“œ SIMILAR VOLUMES

A survey of heuristics for the weighted
A survey of heuristics for the weighted matching problem
โœ David Avis ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 909 KB

This survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Several heuristics are described in detail-and results are given for worst-case ratio bounds, abso

A simple matching algorithm for regular
A simple matching algorithm for regular bipartite graphs
โœ Kazuhisa Makino; Takashi Takabatake; Satoru Fujishige ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 62 KB

We consider the perfect matching problem for a โˆ†-regular bipartite graph with n vertices and m edges, i.e., 1 2 nโˆ† = m, and present a new O(m + n log n log โˆ†) algorithm. Cole and Rizzi, respectively, gave algorithms of the same complexity as ours, Schrijver also devised an O(mโˆ†) algorithm, and the b

A Subquadratic Algorithm for Approximate
A Subquadratic Algorithm for Approximate Regular Expression Matching
โœ S. Wu; U. Manber; E. Myers ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 673 KB

The main result of this paper is an algorithm for approximate matching of a regular expression of size \(m\) in a text of size \(n\) in time \(O\left(n m / \log _{d+2} n\right)\), where \(d\) is the number of allowed errors. This algorithm is the first \(o(m n)\) algorithm for approximate matching t