A distributed memory 1/2-approximation algorithm and heuristic for vertex-weighted matching

We consider maximum vertex-weighted matching (MVM). The MVM problem can be solved both exactly and approximately in polynomial time. Additionally, a parallel approximation algorithm using shared memory was developed to utilize multi-core processors effectively. In this paper, we introduce the first distributed memory 1/2-approximation algorithm for this problem. Furthermore, we introduce a more efficient heuristic for MVM. Although the MVM problem can be addressed using a maximum edge weighted matching (MEM) approximation algorithm, this paper demonstrates that that our heuristic surpasses the fastest MEM approximation algorithm, the Suitor algorithm in terms of both matching quality and computational efficiency.