A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
From MaRDI portal
Publication:2390325
DOI10.1016/j.ipl.2004.05.007zbMath1178.68686MaRDI QIDQ2390325
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
Related Items
A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs, A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs, Approximation algorithms in combinatorial scientific computing, (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings, Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint, Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs, Costly circuits, submodular schedules and approximate Carathéodory theorems, Best of two local models: centralized local and distributed local algorithms, A \(2/3\)-approximation algorithm for vertex-weighted matching, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Weighted matching in the semi-streaming model, Efficient Matching for Column Intersection Graphs, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Near Approximation of Maximum Weight Matching through Efficient Weight Reduction, Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem, Linear-Time Approximation for Maximum Weight Matching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
