Linear-Time Approximation for Maximum Weight Matching: The Approximation Guarantee of the Scaling AlgorithmResearch Paper
The maximum weight matching (MWM) problem asks, for a graph with edge weights, for a set of vertex-disjoint edges of largest total weight. It is a central problem of combinatorial optimization, with applications to transportation, assignment and scheduling, and as a subroutine for shortest paths, planar max cut, Chinese postman tours and metric TSP.…