Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity
We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algorithm on the oblivious matching problem where nodes in a general graph can have arbitrary weights. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors, then it will still be matched even … Read more