Efficient Approximation Algorithms for Weighted $b$-Matching

DOI10.1137/15M1026304zbMath1386.68220MaRDI QIDQ2830632

No author found.

Publication date: 28 October 2016

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsapproximation algorithms\(b\)-matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple ⋮ Multi-agent reinforcement learning for decentralized stable matching ⋮ A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs ⋮ A \(2/3\)-approximation algorithm for vertex-weighted matching ⋮ Approximation algorithms in combinatorial scientific computing

Uses Software

• SparseMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed algorithms for covering, packing and maximum weighted matching
• A simple approximation algorithm for the weighted matching problem
• On the use of optimal fractional matchings for solving the (integer) matching problem
• A polynomial algorithm for b-matchings: An alternative approach
• A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
• The university of Florida sparse matrix collection
• Linear-Time Approximation for Maximum Weight Matching
• A survey of heuristics for the weighted matching problem
• Solving matching problems with linear programming
• Odd Minimum Cut-Sets and b-Matchings
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Random Geometric Graphs
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
• Engineering Algorithms for Approximate Weighted Matching
• Greedy in Approximation Algorithms
• Implementing weighted b-matching algorithms
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Efficient Approximation Algorithms for Weighted $b$-Matching