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.68686OpenAlexW2014533003MaRDI 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
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
- 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
