A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching

DOI10.1016/j.ipl.2004.05.007zbMath1178.68686OpenAlexW2014533003MaRDI QIDQ2390325

Peter Sanders, Seth Pettie

Publication date: 21 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.05.007

zbMATH Keywords

matchingapproximationanalysis of algorithmsmaximum weight matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (17)

Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint ⋮ Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ Costly circuits, submodular schedules and approximate Carathéodory theorems ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Weighted matching in the semi-streaming model ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs ⋮ A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ Near Approximation of Maximum Weight Matching through Efficient Weight Reduction ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ A \(2/3\)-approximation algorithm for vertex-weighted matching ⋮ Efficient Matching for Column Intersection Graphs ⋮ Approximation algorithms in combinatorial scientific computing

Cites Work

• A simple approximation algorithm for the weighted matching problem
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching