3 papers
cs.DS2026
Random Proposals: A Softmax-Based Local-Improvement Framework for Maximum Weighted Matching
Ahmed M. Alzuhair, Ahmed Alherz
We propose a randomized local-improvement algorithm for the Maximum Weighted Matching (MWM) problem. Our method introduces a softmax-based biased sampling mechanism that achieves l…
cs.DS2019
A 2/3-Approximation Algorithm for Vertex-weighted Matching
Ahmed Al-Herz, Alex Pothen
We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs. In earlier work we have described a 2/3-approximation algorithm for the MVM on bipartite gr…
cs.DS2018
A 2/3-Approximation Algorithm for Vertex-weighted Matching in Bipartite Graphs
Florin Dobrian, Mahantesh Halappanavar, Alex Pothen +1
We consider the maximum vertex-weighted matching problem (MVM), in which non-negative weights are assigned to the vertices of a graph, the weight of a matching is the sum of the we…