Efficient approximation algorithms for weighted b-matching
DOI10.1137/15M1026304zbMATH Open1386.68220MaRDI QIDQ2830632FDOQ2830632
Authors: A. Khan, Alex Pothen, Md. Mostofa Ali Patwary, Nadathur Rajagopalan Satish, Narayanan Sundaram, Fredrik Manne, Mahantesh Halappanavar, Pradeep Dubey 
Publication date: 28 October 2016
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)
Cites Work
- The University of Florida sparse matrix collection
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Random Geometric Graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Solving matching problems with linear programming
- A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
- Maximum matching and a polyhedron with 0,1-vertices
- Linear-time approximation for maximum weight matching
- A simple approximation algorithm for the weighted matching problem
- Greedy in Approximation Algorithms
- A polynomial algorithm for b-matchings: An alternative approach
- A survey of heuristics for the weighted matching problem
- Title not available (Why is that?)
- Odd Minimum Cut-Sets and b-Matchings
- Parallel community detection for massive graphs
- Linear time approximation algorithms for~degree~constrained subgraph problems
- Distributed algorithms for covering, packing and maximum weighted matching
- On the use of optimal fractional matchings for solving the (integer) matching problem
- A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem
- Implementing weighted b-matching algorithms
- Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
- Engineering Algorithms for Approximate Weighted Matching
- Graph coarsening and clustering on the GPU
Cited In (15)
- Title not available (Why is that?)
- Approximate Matching in Weighted Sequences
- Greedy in Approximation Algorithms
- Approximation algorithms in combinatorial scientific computing
- A \(2/3\)-approximation algorithm for vertex-weighted matching
- A memetic algorithm to schedule planned maintenance for the national grid
- Efficient algorithms for variants of weighted matching and assignment problems
- Multi-agent reinforcement learning for decentralized stable matching
- Implementing weighted b-matching algorithms
- Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
- A new 3/2-approximation algorithm for the \(b\)-\textsc{Edge Cover} problem
- A parallel 2/3-approximation algorithm for vertex-weighted matching
- An efficient NC algorithm for approximate maximum weight matching
- A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
- A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
Uses Software
This page was built for publication: Efficient approximation algorithms for weighted \(b\)-matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830632)
