A simpler linear time 23 - approximation for maximum weight matching

DOI10.1016/J.IPL.2004.05.007MaRDI QIDQ2390325zbMATH OpenOpenAlexFDO

Authors Seth Pettie, Peter Sanders

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

matchinganalysis of algorithmsapproximationmaximum weight matching

Mathematics Subject Classification ID

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

Recommendations

• Linear-time approximation for maximum weight matching
• A simple approximation algorithm for the weighted matching problem
• Improved linear time approximation algorithms for weighted matchings
• scientific article; zbMATH DE number 1304326
• A linear-time approximation algorithm for weighted matchings in graphs

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• scientific article; zbMATH DE number 1982180 (Why is no real title available?)
• A simple approximation algorithm for the weighted matching problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Faster Scaling Algorithms for Network Problems
• Faster scaling algorithms for general graph matching problems
• Improved linear time approximation algorithms for weighted matchings

Cited in

(24)

• Costly circuits, submodular schedules and approximate Carathéodory theorems
• Best of two local models: centralized local and distributed local algorithms
• A simple approximation algorithm for the weighted matching problem
• scientific article; zbMATH DE number 1982180 (Why is no real title available?)
• Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint
• Efficient matching for column intersection graphs
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• scientific article; zbMATH DE number 1759463 (Why is no real title available?)
• Linear-time approximation for maximum weight matching
• Approximation algorithms in combinatorial scientific computing
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Approximation algorithms for maximum matchings in undirected graphs
• A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
• Linear time approximation algorithms for~degree~constrained subgraph problems
• Multiplicative auction algorithm for approximate maximum weight bipartite matching
• Engineering Algorithms for Approximate Weighted Matching
• A \(2/3\)-approximation algorithm for vertex-weighted matching
• Near approximation of maximum weight matching through efficient weight reduction
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
• Linear programming in the semi-streaming model with application to the maximum matching problem
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
• Weighted matching in the semi-streaming model

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390325)