A simple approximation algorithm for the weighted matching problem

DOI10.1016/S0020-0190(02)00393-9zbMath1173.68861OpenAlexW2024607148MaRDI QIDQ1007528

Stefan Hougardy, Doratha E. Drake

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00393-9

zbMATH Keywords

analysis of algorithmsgraph algorithmsapproximation algorithmsmaximum weight matching

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint ⋮ An enhanced branch-and-bound algorithm for the talent scheduling problem ⋮ Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching ⋮ TRANSPORT IN DYNAMICAL ASTRONOMY AND MULTIBODY PROBLEMS ⋮ Modularity and greed in double auctions ⋮ Local search for constrained graph clustering in biological networks ⋮ Win-win match using a genetic algorithm ⋮ The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ Solving maximum weighted matching on large graphs with deep reinforcement learning ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ Dynamic Matching Algorithms in Practice ⋮ Near Approximation of Maximum Weight Matching through Efficient Weight Reduction ⋮ ASSIGNMENT QUERY AND ITS IMPLEMENTATION IN MOVING OBJECT DATABASES ⋮ Efficient Matching for Column Intersection Graphs ⋮ Advanced Coarsening Schemes for Graph Partitioning ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Efficient Approximation Algorithms for Weighted $b$-Matching

Uses Software

• Blossom IV

Cites Work

• Unnamed Item
• Unnamed Item
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Quality matching and local improvement for multilevel graph-partitioning
• Complexity and modeling aspects of mesh refinement into quadrilaterals
• Faster scaling algorithms for general graph matching problems
• Computing Minimum-Weight Perfect Matchings