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…