A simple approximation algorithm for the weighted matching problem
From MaRDI portal
Publication:1007528
DOI10.1016/S0020-0190(02)00393-9zbMATH Open1173.68861OpenAlexW2024607148MaRDI QIDQ1007528FDOQ1007528
Authors: Doratha E. Drake, Stefan Hougardy 
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00393-9
Recommendations
- A linear-time approximation algorithm for weighted matchings in graphs
- Improved linear time approximation algorithms for weighted matchings
- scientific article; zbMATH DE number 1304326
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Linear-time approximation for maximum weight matching
Cites Work
- Title not available (Why is that?)
- Faster scaling algorithms for general graph matching problems
- Computing Minimum-Weight Perfect Matchings
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Title not available (Why is that?)
- Quality matching and local improvement for multilevel graph-partitioning
- Complexity and modeling aspects of mesh refinement into quadrilaterals
Cited In (35)
- Linear time approximation algorithms for~degree~constrained subgraph problems
- Title not available (Why is that?)
- Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint
- TRANSPORT IN DYNAMICAL ASTRONOMY AND MULTIBODY PROBLEMS
- Title not available (Why is that?)
- Parallel approximation algorithms for maximum weighted matching in general graphs
- Approximation algorithms in combinatorial scientific computing
- Improved linear time approximation algorithms for weighted matchings
- Engineering Algorithms for Approximate Weighted Matching
- Title not available (Why is that?)
- Dynamic Matching Algorithms in Practice
- Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
- A simple PTAS for weighted matroid matching on strongly base orderable matroids
- Linear-time approximation for maximum weight matching
- Win-win match using a genetic algorithm
- Approximation algorithms for weighted matching
- An enhanced branch-and-bound algorithm for the talent scheduling problem
- A simple PTAS for weighted matroid matching on strongly base orderable matroids
- Local search for constrained graph clustering in biological networks
- (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
- A recurrent algorithm to solve the weighted matching problem
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- A new class of heuristic algorithms for weighted perfect matching
- Modularity and greed in double auctions
- Weighted matching as a generic pruning technique applied to optimization constraints
- A \(2/3\)-approximation algorithm for vertex-weighted matching
- ASSIGNMENT QUERY AND ITS IMPLEMENTATION IN MOVING OBJECT DATABASES
- An efficient NC algorithm for approximate maximum weight matching
- The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
- Efficient approximation algorithms for weighted \(b\)-matching
- A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
- Solving maximum weighted matching on large graphs with deep reinforcement learning
- Advanced coarsening schemes for graph partitioning
- Efficient matching for column intersection graphs
Uses Software
This page was built for publication: A simple approximation algorithm for the weighted matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007528)
