Efficient approximation algorithms for weighted b-matching

DOI10.1137/15M1026304MaRDI QIDQ2830632zbMATH OpenFDO

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)

zbMATH Keywords

approximation algorithms\(b\)-matchingparallel algorithms

Mathematics Subject Classification ID

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)

Recommendations

• A linear-time approximation algorithm for weighted matchings in graphs
• scientific article; zbMATH DE number 1759463
• Engineering Algorithms for Approximate Weighted Matching
• scientific article; zbMATH DE number 1304326
• A \(2/3\)-approximation algorithm for vertex-weighted matching

Cites work

• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
• A maximum b-matching problem arising from median location models with applications to the roommates problem
• A polynomial algorithm for b-matchings: An alternative approach
• A simple approximation algorithm for the weighted matching problem
• A survey of heuristics for the weighted matching problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Distributed algorithms for covering, packing and maximum weighted matching
• Engineering Algorithms for Approximate Weighted Matching
• Graph coarsening and clustering on the GPU
• Greedy in Approximation Algorithms
• Implementing weighted b-matching algorithms
• Linear time approximation algorithms for~degree~constrained subgraph problems
• Linear-time approximation for maximum weight matching
• Maximum matching and a polyhedron with 0,1-vertices
• Odd Minimum Cut-Sets and b-Matchings
• On the use of optimal fractional matchings for solving the (integer) matching problem
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Parallel community detection for massive graphs
• Random Geometric Graphs
• Solving matching problems with linear programming
• The University of Florida sparse matrix collection

Cited in

(15)

• A Batch-dynamic Suitor Algorithm for Approximating Maximum Weighted Matching
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• Approximate Matching in Weighted Sequences
• Greedy in Approximation Algorithms
• Approximation algorithms in combinatorial scientific computing
• A \(2/3\)-approximation algorithm for vertex-weighted matching
• Efficient algorithms for variants of weighted matching and assignment problems
• A memetic algorithm to schedule planned maintenance for the national grid
• Multi-agent reinforcement learning for decentralized stable matching
• Implementing weighted b-matching algorithms
• Dominant Z-Eigenpairs of Tensor Kronecker Products Decouple
• An efficient NC algorithm for approximate maximum weight matching
• A new 3/2-approximation algorithm for the \(b\)-\textsc{Edge Cover} problem
• A parallel 2/3-approximation algorithm for vertex-weighted matching
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs

Describes a project that uses

Uses Software

• SparseMatrix

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)