A simpler linear time 23 - approximation for maximum weight matching

DOI10.1016/J.IPL.2004.05.007zbMATH Open1178.68686OpenAlexW2014533003MaRDI QIDQ2390325FDOQ2390325

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

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

zbMATH Keywords

matchinganalysis of algorithmsapproximationmaximum weight matching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• A simple approximation algorithm for the weighted matching problem
• Title not available (Why is that?)
• Improved linear time approximation algorithms for weighted matchings
• Title not available (Why is that?)

Cited In (24)

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

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)